Crisp-cas 9, областная олимпиада по биологии 2018,

Можете объяснить именно пункт Б, пожалуйста


Тип нуклеотида независит от предыдущего нуклеотида: 4/4 (А, Г, Ц, Т) * 1/4(Г) * 1/4(Г)=веротяность встретить такую последовательность * 100 = веротяность встретить такую последовательность среди 100 нуклеотидов

5 симпатий

Я вчера по-моему загнал себя в угол, попытавшись понять, что в этой задаче делать можно и что нельзя. Поэтому хочу задать несколько вопросов, чтобы разобраться.

  1. Может ли быть вероятность больше 1? Я знаю, что у негарантированных событий она может быть 1, но может ли у таких событий она быть больше 1? Событие не гарантировано, потому что как минимум можно придумать последовательность, которая состоит только из А: “ААА…ААА”.

    1. Насколько я понимаю, вероятность, по определению, должна лежать в отрезке от 0 до 1 (0 \leq p \leq 1).

    2. Также вероятностью является доля нужных нам событий среди всех. Но если среди всех комбинаций есть хотя бы несколько комбинаций, в которых наше событие не выполняется, как нужная нам доля может быть > 1?

  2. Можно ли здесь просто умножить на 100?

    1. Как я понимаю, умножать можно если у нас несколько вариантов, из которых должен выполняться хотя бы один. Тогда, если можно умножать, то как мне кажется, надо умножать на 98.

    2. Но есть и другая мысль. Если не ошибаюсь, умножать можно только тогда, когда эти события не могут пересекаться (они должны быть mutually exhaustive), а в этом случае явно есть пересечения между вариантами событий, и умножая на 100 (98), мы все эти пересечения считаем повторно.

Объясню, что я имел ввиду про пересечения. Всего у нас 4^{100} комбинаций. Нужная тройка нуклеотидов может попасться самой первой, а может и второй, и так далее. Поэтому можно посчитать число комбинаций для всех таких случаев и просуммировать их:

NGGNNNN…
NNGGNNN…
NNNGGNN…
NNNNGGN…

Для каждого из этих случаев число комбинаций равно 4^{98}. Самих случаев 98. То есть если мы посчитаем таким образом, у нас выйдет ответ, который мы писали изначально.

P(\text{найти NGG}) = \frac{98 \cdot 4^{98}}{4^{100}} = \frac{98}{16}

Теперь соберем множества из комбинаций для каждого случая. У нас получится 98 множеств. Пересечения, о которых я спрашивал, это те комбинации, которые принадлежат одновременно более чем одному из этих множеств. И каждое из таких пересечений мы считаем как минимум два раза. Приведу пример.

Есть такие комбинации, которые принадлежат и первому и второму множеству (пронумеруем множества в порядке, котором я их писал). Их ровно столько, сколько существует таких комбинаций:

NGGGNNN…

А таких комбинаций бывает 4^{97}. После этого я пытался найти паттерн, по которому можно было бы понять, как учесть пересечения всех 98 множеств, но пока не удалось.

Одно из двух — либо задача довольно трудна для ее решения за 5-10 минут на олимпиаде, либо я себе усложняю жизнь. Хотелось бы понять, что из этого.

ОООО, я делал тоже самое на протяжении 40 минут вчера и так ничего и не понял)))

Я убил часа 2-3 наверное ))

В данном случае ответ будет проще найти через вычитание от 100% (или единицы) вероятность того, что NGG в 100 нуклеотидах присутствовать не будет.
Представим последовательность ДНК состоящую из 100 нуклеотидов. Первыми двумя могут быть любые из четырёх : А, Т, G или C. Вторым основанием может оказаться гуанин, тогда третье не должно быть гуанином, так как в данном случае NGG будет присутствовать в последовательности, что нам не нужно (для понимания N – любой нуклеотид из 4 соответствующих для ДНК). Вероятность того, что гуанин не будет третьим - 3/4. Четвёртым вновь может быть любой нуклеотид, но пятый не должен быть гуанином и так далее. Таким образом, нужно, чтобы в последовательности не было двух G подряд. Первые два основания можно отнять от 100, так как даже если они будут GG, то перед ними нет N. Остается 98, где как мы уже выяснили ранее половина может быть представлена А,Г,Ц или Т, когда другая половина будет с 3/4 вероятностью не являться гуанином. Следовательно, (3/4)^49 - вероятность того, что в последовательности не будет NGG. Тогда ответом будет: 1 - (3/4)^49, что и является решением от Дарына.

4 симпатии

Строго нет.

Да.

А почему? И что именно умножить на 100?

В таких задачах подход должен быть таким: найти общее количество вариантов всех возможных событий, найти кол-во вариантов нужного события и поделить второе на первое.

При этом кол-во вариантов нужного события можно найти так, как показала @tardigrade: идем от обратного или от того, что нужное событие не произойдет ни разу.

Это как раз таки признак того, что найти вероятность того, что событие НЕ существует ПРОЩЕ, чем то, что оно существует. Все таки утверждение «NGG не встречается ни разу» гораздо требовательнее, чем “NGG встречается хоть раз”

Задача трудна тем, что является Гугл переводом. За «сайт» хочется что-то ударить…

Мне кажется, что это решение неверное, потому что не учитывает все случаи, которые нам не подходят. Как я понял, в нем предлагается, что мы берем последовательность из 98 букв, которая не начинается с “G”. И дальше выходит такое произведение:

\frac{3}{4} \cdot 1 \cdot \frac{3}{4} \cdot 1 \cdot \frac{3}{4} \cdot \dots

Тогда есть как минимум два недочета:

  1. Вовсе не обязательно, чтобы последовательность не начиналась с “G”, потому что если во всех последовательности из 100 букв, вторая не является “G”, то третья вполне может ею являться.

  2. В данной последовательности из последних 98 букв, на третьей позиции (так же, как и с последующими) может стоять “G”. Такое будет, если на предыдущей позиции “G” не стоит. То есть как минимум не учитывается такая последовательность: “GNNGNN…”.

В этой задаче в целом будет ошибкой брать события независимыми и перемножать вероятности, потому что события зависимы — вероятность, что следующая буква будет “G” зависит от того, какая буква стоит перед ней.

“NNG” это тоже самое что и “NGG”

что? нет, события полностью независимы.

Зависимость есть только в твоей голове, когда ты пытаешься построить последовательность без фрагментов NGG

Здесь я неправильно обозначил. Я имел ввиду например такую последовательность: “AGAAGATAT…”. Здесь на четвертой позиции не стоит G, а в том решении предлагалось, что G могут стоять только через одну. Но они могут стоять и через две и через три.

Я подвергал сомнению самое первое решение. Там предлагалось 1 \cdot \frac{1}{4} \cdot \frac{1}{4} умножить на 100, что мне казалось неверным.

Учесть все комбинации НЕ тоже не сильно проще. Легко ошибиться и начать считать только конкретные комбинации, в которых G разрешается появляться только на четных или только на нечетных позициях. По крайней мере на данной момент, мне кажется, что оба варианта нахождения вероятности довольно трудные.

В сравнении все таки проще.

Это всегда верно)

Заметь, я не говорил, что уверен, что решение @tardigrade правильное. Я вижу откуда идут твои сомнения.

Попробую так же пойти от обратного, но немного своим ходом.

Если я не ошибаюсь (а я могу ошибаться), то задачу можно свести от “найти вероятность того, что в последовательности из 100 нуклеотидов нет ни одного фрагмента NGG” к “найти вероятность того, что в последовательности из 99 нуклеотидов нет ни одного фрагмента GG”.

Если мы можем разбить новую последовательность на пары (а у нас будет 49 пар + 1 нуклеотид), то на каждую пару у нас есть 15/16 вариантов (за исключением GG).

Т.е. как будто бы (15/16)^{49}. Но есть нерешенные вопросы.

  1. Что с последним нуклеотидом?
    Два варианта: либо предпоследний нуклеотид кончается на G либо не кончается.
    1.1. Кончается на G: тогда 3/4 вариантов
    1.2. Не кончается на G: тогда 1 вариант
    Какова вероятность что он кончается на G? (3/16) (мы не учитываем пару GG)
    Какова вероятность он не кончается на G? (12/16)=3/4

Теперь главное: как совместить эту информацию с вероятностями пар?

и второй вопрос:

  1. Потеряли ли мы общность когда начали считать пары с первого нуклеотида? Если бы мы начали со второго? Кажется что нет, потому что в любом случае мы остаемся с 1 нуклеотидом + 49 пар, а в каком конце этот нуклеотид разницы не должно быть.

Я пока не дошел до ответа на первый вопрос, но решил вылить рассуждения, может кто дойдет быстрее.

1 симпатия

Может быть?

\frac{15}{16}^{49}\cdot\left[ \frac{3}{16}\frac{1}{4}+\frac{3}{4} \right] = \frac{15}{16}^{49} \frac{51}{64}

Не говорю, что так переформулировать задачу нельзя, но мне кажется не стоит лезть в эти дебри) Как минимум потому, что в таком случае получается почти идентичная задача. Проблема в том, что деля все на пары, ты упускал некоторые комбинации, например:

AGGTGATGGA…

Если поделить все на пары, то получатся [‘AG’, ‘GT’, ‘GA’, ‘TG’, ‘GA’]. Здесь нигде нет ‘GG’, но во всей последовательности она все равно встречается.

Вот если сместить учет пар на одно деление вправо, получим:

[‘A’, ‘GG’, ‘TG’, ‘AT’, ‘GG’, ‘A’]

Это то, о чем я говорил во втором вопросе. По идее уникальных делений на пары только два, так что может все таки можно как-то найти решение через этот способ?

1 симпатия

Я тогда тоже поделюсь своими пока незаконченными рассуждениями. Можно разделить все нежелательные исходы на три группы, которые не пересекаются:

  1. В последовательности нет G
  2. Есть какое-то количество G, и все они находятся на расстоянии как минимум 1 буквы
  3. Есть только одна ‘GG’, которая занимает только первые две позиции

Для первого и третьего случая посчитать нетрудно. В первом случае это просто 3^{100}, а в третьем — 3^{98}. Сейчас я пытаюсь понять, как можно найти число комбинаций для второго случая. Пробую посчитать это число для коротких последовательностей и потом вывести для общего случая, при длине в n букв.

А это прям красиво получилось. Я попытался продолжить твой ход, но пришел к еще одной проблеме. Мы не учитываем порядок пар. Он тоже может меняться. И казалось бы, что можно просто умножить на число перестановок этих 49 пар и 1 нуклеотида, но тогда вопрос — сколько таких перестановок?

У нас какие-то пары будут встречаться по несколько раз, такие варианты надо будет отсекать, но их количество зависит от того, какая пара повторяется и сколько раз она повторяется. Может получиться, что все 49 пар являются ‘AA’, а может получиться, что ‘AA’ повторяется 40 раз и ‘TT’ повторяется 9 раз. В каждом случае считать по-разному.

Вчера у меня стоял похожий вопрос и тогда я подумал, а что если через какое-то распределение выразить то, сколько будет какая-то пара повторяться? Тогда к каждому такому случаю можно было бы написать свое произведение, но это звучит как-то нереально, не могу даже представить, что там выйдет.

ED: я сейчас понял, что нам порядок и не важен, тогда все нормально

если мы считаем все возможности пар, то это уже включает повторяющиеся пары и их перестановки. Так что домножать не нужно)

Как насчет такого конечного ответа:

1 - \left[ \left( \frac{15}{16} \right)^{49} \cdot \left( \frac{3}{15}\cdot \frac{3}{4} + \frac{12}{15} \right) \right]^2

49 пар без ‘GG’. Потом 49-я пара либо имеет G на конце (тогда последним может быть любой из остальных трех), либо не имеет. И возвести в квадрат, потому что и при первом делении, и при втором, это все должно выполняться. А сами деления симметричны, поэтому можно взять одинаковые вероятности для них.

Во второй скобке поставил 15, потому что слева степень 49-я, значит уже все пары без ‘GG’, то есть выбирать осталось только среди 15 вариантов. 16 должно стоять если слева будет 48-я степень, мне кажется.

Если они одинаковые, то надо помножить на два, а не делить.

Не совсем понял откуда ты взял 12/15. Если продолжать мою мысль, то финальный ответ:

1-4\cdot k \cdot \frac{15}{16}^{49} \frac{51}{64}

Где k=1 или k=2 в зависимости от того перемножаем мы на два за счет другого деления или нет. На 4 множим т.к. первый нуклеотид (в последовательности из 100) может быть любым из четырех.

Ответ @tardigrade 0.999\,999\,245

Если посчитать мое с k=2: 0.730\, 180\, 873

Давай теперь подумаем насколько это физически имеет смысл?