Компьютерное дополнение к курсу Информатика 6. 2017

Урок 32. «Биоинформатика. Как изучают белки. Сравнение белков. Превращение слов»

К настоящему моменту дети уже получили представление о том, как устроено кодирование в ДНК. Однако нам бы не хотелось, чтобы у ребят осталось впечатление, что в биоинформатике все так же просто, как в наших задачах. На самом деле в биоинформатике есть серьезные проблемы, над которыми сегодня работают ученые-биологи. На этом листе определений мы очень кратко и в общих чертах постарались обозначить эти проблемы. Первая – определение начала гена. Дело в том, что конец гена определяется однозначно, поскольку стоп-кодоны не кодируют больше никаких белков. При этом старт-кодон может в других случаях кодировать белок (метионин), поэтому встречается внутри гена. Таким образом, отделить гены от окружающего «шума» бывает не так просто. Вторая проблема – перекрывающееся кодирование. Как ребята могли убедиться в ходе решения задач, расшифровать такую шифровку сложнее, поскольку для каждого из перекрывающихся участков надо правильно определить начало. Третья проблема – ошибки кодирования. По некоторым причинам иногда в ДНК отдельные нуклеотиды теряются или вставляются лишние или происходит то и другое. Найти такую ошибку (и, соответственно, правильный шифр) тоже бывает непросто. В наших задачах все эти проблемы решались не слишком сложно на основании принятых нами договоренностей. Например, старт-кодон (код начала предложения) у нас шифрует начало предложения однозначно, поэтому проблема поиска начала шифровки стоит не так остро. При поиске ошибок и расшифровке с перекрытием мы используем то, что в результате должны получиться осмысленные слова русского языка или сравниваем сразу несколько шифровок. Ясно, что в биологии все эти соображения работать не будут. Как же решают перечисленные проблемы биологи? В биоинформатике при расшифровке ДНК очень помогает сравнение родственных белков. При этом новая шифровка сопоставляется с цепочкой белков ближайшего родственника, которая уже расшифрована. Об этом мы поговорим с ребятами на следующем уроке.

 

Задача 218. Шифровка первого слова начинается с первой буквы и составляет всего 12 символов (слова у нас из 4 букв). Значит, его код – CAACGAAGTTAA. Получаем, что зашифровано слово ЖЮРИ. Ясно также, что с 13 символа и до конца идет только шифровка второго слова. Отсчитываем 12 символов с конца слова – это шифровка второго слова – GAAGTTAAACAT. Значит, зашифровано слово ЗЛАЯ.

Задача 219. Сосчитаем, сколько всего существует способов зашифровать слово МОЩЬ. Самый простой способ – построить дерево перебора вариантов. Слабым детям лучше посоветовать нарисовать дерево. Сильные ученики, скорее всего, смогут представить, описать дерево и сосчитать число его последовательностей, не строя дерева. Итак, на первом уровне у нас будут располагаться все коды буквы М, таких у нас три (ACG, GCA, TTT). Дети каждой из этих элементов первого уровня – коды буквы О, таких тоже три (АСТ, ТТА, ТТС), значит, на втором уровне в нашем дереве 9 элементов. Дети каждой из них – все коды буквы Щ, у нас такой один (GСС), значит, на третьем уровне будет снова 9 элементов. За каждой из них должны следовать все коды буквы Ь, такой код у нас один (СТТ), значит, на четвертом уровне дерева перебора будет 9 элементов. В результате оказывается, что в дереве перебора 9 последовательностей, их набор и дает нам множество всех шифровок слова МОЩЬ. В данной задаче дети должны выписать ровно 6 из этих шифровок.

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

Ответ: существует 16 способов зашифровать слово ЖАДНЫЙ:

 

CAAAAAACAAGCCGGACC CAAAAAACAGTACGGACC CAAAAAGGCAGCCGGACC CAAAAAGGCGTACGGACC CAAGAGACAAGCCGGACC CAAGAGACAGTACGGACC CAAGAGGGCAGCCGGACC CAAGAGGGCGTACGGACC

CAAGACACAAGCCGGACC CAAGACACAGTACGGACC CAAGACGGCAGCCGGACC CAAGACGGCGTACGGACC CAAGATACAAGCCGGACC CAAGATACAGTACGGACC CAAGATGGCAGCCGGACC CAAGATGGCGTACGGACC

 

Задача 221. Необязательная. Это третья, последняя задача с биологическим сюжетом. Поскольку для ее решения важно понимать особенности процесса кодирования в ДНК, а мы не можем требовать этого от всех детей, эта задача помечена как необязательная.

Для решения задачи требуется сначала хорошо разобраться в задании, описании закономерности. После этого найти два исключения из этой закономерности будет нетрудно. В обратной таблице генетического кода, помещенной на форзаце учебника, кодоны расположены в алфавитном порядке, поэтому закономерность, о которой говорится в задаче, хорошо видна: ее можно проследить по колонке с остатками. Видно, что остатки часто стоят подряд – по 4 и по 2. Там, где 4 одинаковых остатка подряд, первые две буквы кодонов одинаковы. Там, где два одинаковых остатка подряд, первые две буквы кодонов одинаковы, а третьи буквы – либо A и G, либо C и T. И есть ровно два места, где такая закономерность не выполняется: пары кодонов ATA, ATG и TGA, TGG обозначают разные

остатки.

Ответ: ATA и ATG – изолейцин и метионин; TGA и TGG –

стоп-кодон и триптофан.

Задача 222. Сложная задача, предназначенная, главным образом, для сильных учеников, слабые дети могут ее пропустить. Любая шифровка слова РЫСЬ заканчивается тройкой символов СТТ. Коды буквы Л (из слова ПЕЛ) – АТТ и GТТ, значит, одна вычеркнутая буква – это С (из кода Ь). Последний символ в кодах буквы С (АТG, TCT, TGC) – это G, Т или С, значит, из кодов буквы Л (слова ПЕЛ) нам подходит GТТ, а из кодов буквы С (слова РЫСЬ) нам подходит АТG. Для буквы Ы у нас есть только один код, значит, последние 9 символов кода слова РЫСЬ – СGGАТGСТТ. Итак, сейчас для слова РЫСЬ возможны два варианта шифровок – АGTСGGАТGСТТ и ТАТСGGАТGСТТ. Вычеркнем из них уже известную С (из кода Ь). Получаем АGTСGGАТGТТ и ТАТСGGАТGТТ.

Попробуем вычеркнуть из этих шифровок 2 буквы так, чтобы получилась шифровка слова ПЕЛ. Возьмем шифровку ТАТСGGАТGТТ. Сравниваем первые символы (3–5 символов) с кодами буквы П.

Случай 1. Вычеркнем первую букву Т. Получаем АТС (код П)–GGАТ–GТТ (код Л). Теперь, если из второй части шифровки (четверки GGАТ) вычеркнуть А, то получим один из кодов слова ПЕЛ – АTСGGТGТТ.

Случай 2. Вычеркнем вторую А. Тогда, чтобы получить один из кодов слова ПЕЛ, нужно вычеркнуть и С. Получаем код ТТG (код П)–GАТ–GТТ (код Л). При этом GАТ не является кодом буквы Е, поэтому этот случай не приводит нас к решению.

Возьмем шифровку АGTСGGАТGТТ. Сравниваем первые символы (3–5 символов) с кодами буквы П. Получаем, что необходимо вычеркнуть вторую G. Получаем АTС (код П)–GGАТ–GТТ (код Л). Теперь если из второй части кода (четверки GGАТ) вычеркнуть А, то получим один из кодов слова ПЕЛ – АTСGGТGТТ.

В результате мы получаем 2 решения: АGTСGGАТGСТТ и ТАТСGGАТGСТТ.

Задача 223. Необязательная. Задача, обратная задачам 219 и 220. Надеемся, что после их решения здесь ребенку уже не потребуется дерево перебора, чтобы обосновать, что способов действительно больше 10, ведь обосновать свой ответ можно и рассуждениями.

Задача 224. Аналогичные задачи ребята уже решали. Отличие данной задачи лишь в том, что теперь дети пользуются полным (неоднозначным) шифром, поэтому разные коды могут обозначать одну букву.

Ответ: УРОК МУЗЫКИ ПЕРЕНОСИТСЯ НА ЗАВТРА

Задача 225. Необязательная. Задача аналогична задаче 171. Дерево перебора будет строиться следующим образом – на первом уровне будут 4 цифры, у каждой из них – трое детей, у каждой вершины второго уровня – двое детей, у каждой вершины третьего уровня – один ребенок.

Ответ: переставляя цифры числа 9854, можно получить 24 числа.

 

Биоинформатика. Сравнение белков. Превращение слов

Сравнение белков

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

Сравнение белков – важный метод биоинформатики. Он решает две основные проблемы. Если известна степень родства видов, то он помогает в расшифровке ДКН в сложных случаях (см. наш комментарий к предыдущему листу определений). Если ДНК расшифрована и имеются две цепочки белков, то сравнение белков помогает установить степень родства видов. Именно такой пример подробно описан на листе определений – сравнивая белковые цепочки, ученые получили важный результат о степени родства африканских и индийских слонов.

Как и при рассмотрении кодирования в ДНК, в этой теме, к сожалению, не удается раскрыть проблему целиком на биологическом материале. Настоящая биоинформатическая таблица сравнения белков оказывается слишком сложной и громоздкой. Кроме того, не хочется перегружать учеников 6 класса чрезмерно большим количеством разных биологических деталей. Поэтому, как и задачу кодирования в ДНК, мы рассматриваем задачу сравнения белков в модели. В качестве модели мы берем сравнение двух русских слов. На самом деле такая модель неплохо отражает содержание исходной проблемы.

Как и в предыдущих уроках, посвященных биоинформатике, в результате этого урока дети должны хорошо разобраться в «учебном» листе определений («Превращение белков») и уметь решать основные задачи на превращение слов. Что касается биологического содержания – дети должны понимать ключевые моменты: что сравнение белков позволяет решать важные биологические проблемы, связанные с белковыми цепочками родственных видов и что сравнение белков производится примерно так же, как в наших задачах на превращение слов.

 

Превращение слов

Первая часть данного листа определений – «учебный» лист определений. Именно здесь содержится вся информация, которая понадобится ребятам для решения задач. Рассмотренная здесь игра несколько выпадает из ряда тех, которые мы рассматривали в нашем курсе. В этой игре участвует только один игрок и нет победителя и проигравшего. Мы анализируем эту игру не с точки зрения выигрыша и проигрыша, а по другим параметрам. Сама игра настолько несложная, что трудностей не вызовет даже у слабых учащихся.

Вторая часть данного листа определений – это продолжение обсуждения биологических проблем, т. е. раздела «Сравнение белков». Здесь необязательно добиваться от детей полного понимания, этот текст написан для общего развития детей и для завершения биологической картины обсуждаемой проблемы.

Для ученых-биологов задача сравнения белков равнозначна задаче поиска наиболее дешевого превращения. Действительно, цены всех замен и вставок в биологии были выяснены опытным путем. Соответствующие числа тем меньше, чем больше вероятность именно такого события в ходе размножения особей и эволюции видов. Поэтому именно наиболее дешевые превращения отражают процесс эволюции видов, который может протекать с наибольшей степенью вероятности. Заметим, что мы в наших задачах не можем ставить задачу поиска наиболее дешевого превращения как учебную. Задачи на поиск оптимального варианта в 6 классе могут решаться только при помощи полного перебора, а здесь перебор будет чрезмерно большим. Все остальные способы решения такой задачи требуют привлечения математического аппарата, который для 6 класса оказывается недоступным. В частности, в каждой такой задаче помимо приведения наиболее дешевого превращения необходимо приводить доказательство того, что это превращение является наиболее дешевым. Такие задачи можно было бы предложить сильным детям, у нас в курсе подобных задач немного. В наших задачах мы, в основном, всего лишь просим ребят построить какое-нибудь превращение слов, необязательно самое дешевое.

Задача 226. Это задача, позволяющая лучше понять материал листа определений «Превращение слов» (точнее, его «учебной» части). Здесь, как и в большинстве задач этого урока, мы просим детей построить какое-нибудь, любое превращение слов, хотя, конечно, в биоинформатике реальную ценность представляет самое дешевое превращение. Как же приблизить детей к решению (и пониманию!) реальной биологической задачи, но при этом избежать сложных обсуждений, к которым не готова основная масса ребят. Попробуйте организовать решение этой задачи (и подобных ей) в виде игры. Для начала пусть каждый построит свое превращение и оформит решение задачи в тетради. Затем можно опросить детей и выяснить различные стоимости превращений, которые получились у ребят в классе. Затем из этих стоимостей надо выбрать самую меньшую. Если вы видите, что эта стоимость в данном случае будет на самом деле минимальной, попросите ребят построить превращение с такой стоимостью (если получится не у всех – не страшно). Если среди всех вариантов в классе наименьшей стоимости не обнаружилось, попросите ребят построить еще одно превращение, стоимость которого будет меньше первого, а затем повторите обсуждение. В чем смысл такой работы? Во-первых, по ходу дела дети учатся строить не просто превращения, а наиболее дешевые превращения. Во-вторых, вы в ходе решения каждой задачи будете искать наиболее дешевое превращение среди тех, которые имеются в классе. Среди решений в ходе опроса вы, по сути, проводите полный перебор, поэтому никакого доказательства минимальности в строгом смысле здесь проводить не нужно, ведь вы не утверждаете, что вообще не существует более дешевых превращений. Если даже после повторного поиска более дешевого превращения ни у кого из детей не обнаружилось самое дешевое превращение (в строгом смысле), можете предложить самое дешевое превращение сами.

Вот одно из превращений, соответствующих условию (серым помечены буквы, которые подвергались удалению или замене):

ТАНКИСТ–ТАНИСТ–ТУНИСТ–ТУРИСТ

Стоимость данного превращения равна 8. Это одно из самых дешевых превращений (существует несколько превращений со стоимостью 8).

Задача 227.

Ответ: Стоимость превращения G равна 13, стоимость пре вращения Q равна 10, значит, превращение Q – более дешевое.

Задача 228. Задача, аналогичная задаче 226. Вот одно из подходящих превращений (серым помечены буквы, которые подвергались удалению или замене):

ВРАЗБРОС – ВРАЗРОС – ВРАЗРЕС – ВРАЗРЕЗ.

Стоимость данного превращения равна 8. Это одно из самых дешевых превращений слова ВРАЗБРОС в слово ВРАЗРЕЗ.

Задача 229. Конечно, эта задача сложнее, чем 226 и 228, здесь нужно построить не какое-нибудь превращение, а превращение заданной стоимости (на самом деле, это самое дешевое превращение). Аналогичной работой вы могли заниматься и в задачах 226, 228, но в качестве дополнительного задания или игры, там эта работа могла вестись с расчетом на сильных детей. Эта же задача предназначена для всех, а значит, нужно постараться достичь понимания. В качестве указания мы предлагаем ребятам построить выравнивание слов. Построить выравнивание – это значит попросту сделать слова равной длины, вставив в слово меньшей длины черточки. Однако черточки можно вставить по-разному, в зависимости от этого для каждого выравнивания получается превращение определенной стоимости. Нам нужно превращение стоимости 10, и мы должны вставить в слово КОНТАКТ одну черточку. Буква с номером, соответствующим месту черточки в слове КОНТАКТ, в слове КОМПЛЕКТ будет подлежать удалению. Все остальные пары букв на соответствующих местах мы будем сравнивать и считать стоимости превращений по количеству и характеру произошедших замен. Таким образом, в этой задаче ребята узнают, что превращение слов можно оформить не только в виде последовательности превращения, но и в виде выравнивания. В данной задаче можно воспользоваться методом полного перебора. Как сказано в указании, выравнивание строится так, чтобы одинаковые буквы стояли друг под другом (с точки зрения биоинформатики это соображение становится очевидным). Значит, черточку в данном случае имеет смысл поставить в слове КОНТАКТ на третьем, четвертом, пятом и шестом местах. Случай, когда черточка на шестом месте, рассмотрен в условии – он не подошел. Рассматриваем все оставшиеся варианты, подходящим оказывается выравнивание, где букву надо вставить на пятое место. Получаем следующее превращение стоимостью 10 (серым помечены буквы подлежащие заменам):

КОНТ-АКТ–КОНТЛАКТ–КОНТЛЕКТ–КОМТЛЕКТ–КОМПЛЕКТ

Задача 230. Необязательная. Рассматривая строение фигуры У, выясняем, что каждая из одинаковых частей должна состоять  из трех целых клеток и трех половинок. Наиболее правдоподобным кажется соображение, что все три верхние клетки принадлежат одной из фигур, оно в данном случае оказывается верным.

Ответ: 

Задача 231. Необязательная. Эта задача аналогична тем, которые решались в проекте «Метод половинного деления». Построим самую длинную последовательность числа элементов дерева сортировки Половинным разделителем чисел от 1 до 1000. Получаем:

1000–500–250–125–63–32–16–8–4–2–1.

Значит, высота соответствующего дерева сортировки равна 11, а для угадывания числа от 1 до 1000 понадобится 10 вопросов

Задача 232. Задача, аналогичная задаче 229, предполагающая построение выравнивания и применение метода полного перебора. Вот одно из подходящих превращений (серым помечены буквы, подлежащие удалению или замене):

СЪЕДОБНЫЙ–СЕДОБНЫЙ–ОЕДОБНЫЙ–ОГДОБНЫЙ–ОГРОБНЫЙ–ОГРОМНЫЙ

Задача 233. В этой задаче на стоимость превращения указано только то, что она должна быть меньше 10. Задача может быть решена аналогично задаче 229 – полным перебором всех возможных выравниваний. Можно решить эту задачу и с помощью рассуждений, например таких. В слове ПОЛЬСКИЙ совершенно точно одну букву придется убрать. Очевидно, это должна быть одна из первых четырех букв, поскольку концы слов совпадают. Если эта буква – не Ь, то потом придется еще менять мягкий знак на другую букву. Уже две эти операции дают нам 9 баллов, а превращение еще не закончится. Значит, надо удалять в слове ПОЛЬСКИЙ букву Ь. Дальше необходимо заменить в двух местах согласную на согласную. Получаем превращение стоимостью 9 баллов. Оно нам подходит, в данном случае оно будет самым дешевым.

Задача 234. Необязательная. Первое задание ребята уже выполняли, решая задачу 229. Здесь можно поступить так же – строить все возможные выравнивания, пока мы не встретим выравнивание, для которого стоимость соответствующего превращения равна 11.

Второе задание, как мы говорили, предназначено, в основном, для сильных учащихся. Это единственная задача, где мы предлагаем ребятам подумать над доказательством минимальности стоимости превращения. Доказательство здесь можно провести двумя способами. Первый – довести полный перебор выравниваний до конца, для каждого выравнивания посчитать его стоимость и убедиться, что меньшей стоимости не существует. Второй – провести некоторые рассуждения, например такие. В данных словах есть 7 пар совпадающих букв на соответствующих местах (с учетом выравнивания). Если отбросить эти буквы, то в слове ПОДБЕРЕЗОВИК остается 5 букв (БЕРЁЗ), каждая из которых не совпадает с оставшимися буквами слова ПОДОСИНОВИК (ОСИН). Одну букву к части ОСИН придется добавить и все эти буквы придется заменить. При этом, чтобы заменить две гласные, нам понадобится истратить самое меньшее 2 балла (если мы будем заменять их на гласные). Чтобы заменить 2 согласные, нам придется истратить самое меньшее 4 балла (если заменять их на согласные). Из этих рассуждений становится ясно, что невозможно построить превращение дешевле 11 баллов. Вот одно из подходящих, наиболее дешевых превращений:

ПОДОСИНОВИК–ПОДБОСИНОВИК–ПОДБЕСИНОВИК–  ПОДБЕРИНОВИК–ПОДБЕРЁНОВИК–ПОДБЕРЁЗОВИК