Сущность биоинформатики

Министерство Образования Республики Беларусь

Учреждение Образования «Белорусский Государственный Университет Транспорта»

Кафедра «Информационные  технологии» 

ДОКЛАД

по дисциплине:

динамическое программирование

тема: Биоинформатика

Выполнила:        Проверила:

студентка группы ЭМ-21      преподаватель

Гулевич А.А.        Миняйлова Е.Л.

Гомель 2011

Что такое биоинформатика?

В настоящее время слово  биоинформатика стало очень модным, оно употребляется в трех разных смыслах. Первый смысл связывают  с телепатией, экстрасенсорикой и т.д. Второй смысл связан с применением компьютеров для изучения любого биологического объекта. И третий - биоинформатика в узком смысле слова, а именно о применении компьютерных методов для решения задач молекулярной биологии, в основном анализа разных последовательностей (аминокислотных, нуклеотидных).

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

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

В биоинформатике используются методы прикладной математики, статистики и информатики.

Эта наука возникла в 1976-1978 годах, главным образом в связи с работами по расшифровке генома человека, окончательно оформилась в 1980 году со специальным выпуском журнала «Nucleic Acid Research» (NAR). Биоинформатика включает в себя:

• базы данных, в которых хранится биологическая информация;
• набор инструментов для анализа тех данных, которые лежат в таких базах;
• правильное применение компьютерных методов для правильного решения биологических задач.

Термины биоинформатика и  «вычислительная биология» часто  употребляются как синонимы, хотя каждый автор в данной области  придумывает, как правило, свои собственные  определения для каждого. Иногда считают, что не всякое использование  вычислительных методов в биологии является биоинформатикой, например, математическое моделирование биологических процессов — это не биоинформатика.

Немного из истории

Биоинформатика возникла в конце 70-х годов на стыке молекулярной биологии и генетики, математики (статистики и теории вероятности) и информатики, испытавшая влияние лингвистики и физики полимеров. Толчком к этому послужило появление быстрых методов секвенирования последовательностей ДНК. (Секвенирование (от англ. Sequence – последовательность) — определение первичной аминокислотной или нуклеотидной последовательности биополимеров (белков и нуклеиновых кислот – ДНК и РНК). В результате получается линейное символьное описание, которое сжато поясняет атомную структуру молекулы.) Нарастание объема данных происходило лавинообразно и довольно скоро стало ясно, что каждая полученная последовательность не только представляет интерес сама по себе (например, для целей генной инженерии и биотехнологии), но и приобретает дополнительный смысл при сравнении с другими. В 1982 году были организованы банки данных нуклеотидных последовательностей - GenBank в США и EMBL в Европе. Первоначально данные переносились в банки из статей вручную, однако, когда этот процесс начал захлебываться, все ведущие журналы стали требовать, чтобы последовательности, упоминаемые в статье, были помещены в банк самими авторами. Многие последовательности сейчас попадают в банки без публикации. Банки постоянно обмениваются данными и, в этом смысле, практически равноценны, однако средства работы с ними, разрабатываемые в Центре биотехнологической информации США и Европейском институте биоинформатики, различны. Пожалуй, первым биологически важным результатом, полученным при помощи анализа последовательностей, было обнаружение сходства вирусного онкогена v-sis и нормального гена фактора роста тромбоцитов, что привело к значительному прогрессу в понимании механизма рака. С тех пор работа с последовательностями стала необходимым элементом лабораторной практики.

В 1995 году был секвенирован первый бактериальный геном, в 1997 - геном дрожжей. В 1998 было объявлено о завершении секвенирования генома первого многоклеточного организма - нематоды. По состоянию на 1 сентября 2001 года доступны 55 геномов бактерий, геном дрожжей, практически полные геномы Arabidopsis thaliana (растения, родственного горчице), нематоды, мухи дрозофилы - все это стандартные объекты лабораторных исследований. Количество геномов, находящихся в распоряжении фармацевтических и биотехнологических компаний, оценить трудно, хотя, по-видимому, оно составляет многие десятки и даже сотни. (Информации даже о примерном количестве расшифрованных геномов на данный момент нет. Последние сведения в сети интернет повествуют, только то, что к марту 2011 года уже расшифровано около 200 геномов людей (различных национальностей и расовой принадлежности), а также большинство известных вирусов.) Ясно, что подавляющее большинство генов в этих геномах никогда не будет исследовано экспериментально. Поэтому компьютерный анализ и становится основным средством изучения.

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

Следует отметить, что многие задачи из разных областей решаются сходными алгоритмами.

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

В настоящее время существует специальная литература по биоинформатике, проходят международные конференции, ведутся разработки новых алгоритмов и поиск новых путей решения задач биоинформатики. Так, например, основные журналы по биоинформатике - «Bioinformatics», «Journal of Computational Biology» и «Briefings in Bioinformatics», конференции - ISMB (Intellectual Systems for Molecular Biology) и RECOMB (International Conference on Computational Biology).

Коротко об основных областях исследований

Анализ  генетических последовательностей

Обработка гигантского количества данных, получаемых при секвенировании, является одной из важнейших задач биоинформатики

C тех пор как в 1977 году был секвенирован фаг Phi-X174, последовательности ДНК всё большего числа организмов были дешифрованы и сохранены в базах данных. Эти данные используются для определения последовательностей белков и регуляторных участков. Сравнение генов в рамках одного или разных видов может продемонстрировать сходство функций белков или отношения между видами (таким образом могут быть составлены Филогенетические деревья). В наши дни для поиска по геномам тысяч организмов, состоящих из миллиардов пар нуклеотидов используются компьютерные программы. Программы могут однозначно сопоставить (выровнять) похожие последовательности ДНК в геномах разных видов; часто такие последовательности несут сходные функции, а различия возникают в результате мелких мутаций, таких как замены отдельных нуклеотидов, вставки нуклеотидов, и их «выпадения» (делеции). Один из вариантов такого выравнивания применяется при самом процессе секвенирования. Так называемая техника «дробного секвенирования» (которая была, например, использована Институтом Генетических Исследований для секвенирования первого бактериального генома, Haemophilus influenzae) вместо полной последовательности нуклеотидов даёт последовательности коротких фрагментов ДНК (каждый длиной около 600—800 нуклеотидов). Концы фрагментов накладываются друг на друга и, совмещённые должным образом, дают полный геном. Такой метод быстро даёт результаты секвенирования, но сборка фрагментов может быть довольно сложной задачей для больших геномов. В проекте по расшифроке генома человека сборка заняла несколько месяцев компьютерного времени. Сейчас этот метод применяется для практически всех геномов, и алгоритмы сборки геномов являются одной из острейших проблем биоинформатики на сегодняшний момент.

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

Биоинформатика помогает связать геномные и протеомные проекты, к примеру, помогая в использовании последовательности ДНК для идентификации белков.

Аннотация геномов

В контексте геномики аннотация — процесс маркировки генов и других объектов в последовательности ДНК. Первая программная система аннотации геномов была создана в 1995 году Оуэном Уайтом (англ. Owen White), работавшим в команде, секвенировавшей и проанализировавшей первый декодированный геном свободноживущего организма, бактерии Haemophilus influenzae. Доктор Уайт построил систему для нахождения генов, тРНК и других объектов ДНК и сделал первые обозначения функций этих генов. Большинство современных систем работают сходным образом, но эти программы постоянно развиваются и улучшаются.

Вычислительная  эволюционная биология

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

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

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

Оценка  биологического разнообразия

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

Часто из области рассмотрения биоинформатики выпадают методы оценки других компонентов биоразнообразия — таксонов (в первую очередь видов) и экосистем. В настоящее время математические основания биоинформационных методов для таксонов представлены в рамках такого научного направления как Фенетика, или численная таксономия. Методы анализа структуры экосистем рассматриваются специалистами таких направлений как системная экология, биоценометрия.

Примеры

Теперь перейдем к рассмотрению инструментов биоинформатики и непосредственному применению динамического программирования (на примере выравнивания последовательностей). Инструменты определяются задачами, которые хотят решать.

Основу биоинформатики составляют сравнения. Если у нас есть, например, аминокислотная последовательность, о которой у нас есть экспериментальные данные, и известны ее функции, и другая, похожая на нее последовательность, мы можем предположить, что эти последовательности выполняют сходные функции. Это задача поиска сходства последовательностей

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

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

Как оценить "правильность" метода? Геном типичной бактерии содержит около 1000 генов. Как уже упоминалось, секвенировать геном можно за неделю. Экспериментальная характеристика одного белка требует как минимум 2 месяца работы современной лаборатории.

Для того, чтобы определить, насколько предложенный метод анализа хорош и правилен, существует так называемый «золотой стандарт». Например, у нас есть метод определения генов. Если после его применения на какой-либо последовательности, в которой известно месторасположение генов, наши результаты совпадают с тем, что есть на самом деле на 80-90%, значит наш метод правильный и эффективный. В этом и заключается суть «золотого стандарта».

Или предсказание вторичной  структуры РНК. Экспериментально ее определить очень трудно, но есть РНК, структура которых хорошо известна – это рРНК и тРНК. И если наш метод хорошо предсказывает структуру этих известных РНК, то можно ожидать, что и для других РНК он будет давать хорошие предсказания.

Вернемся к первой задаче – сравнению последовательностей. Запишем одну последовательность под  другой.

attgtACcTCgTgG-AA----

-----AC-TCaTaGcAAccag

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

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

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

Поэтому при сравнении  аминокислотных последовательностей  учитывают также матрицу сопоставления  аминокислотных остатков (похожих, менее  похожих и совсем непохожих).

Итак, как осуществляется выравнивание?

Пишем одну последовательность под другой.

Найдем, сколько есть способов написать одну последовательность S1 длиной m под другой – S2 длиной n (со вставками).

Построим выборочную последовательность S длиной m+ n следующим образом: возьмем несколько символов из последовательности S1, потом несколько символов из последовательности S2 потом опять несколько символов из S1, потом опять несколько из S2.

–Каждой выборочной последовательности S соответствует выравнивание и по каждому выравниванию можно построить выборочную последовательность.

–Количество выборочных последовательностей равно

Таким образом количество выравниваний можно определить по формуле:

А как же найти оптимальное среди такого большого количества? Можно, конечно, попробовать разные способы, но оказывается, что этот поиск сводится к задаче поиска оптимального пути на графе. Задача поиска оптимального пути на графе решается методами динамического программирования следующим образом. Мы пишем одну последовательность над другой. И у нас есть некая ячейка, в которой мы будем хранить вес наилучшего выравнивания префиксов (то фрагментов последовательности от начала до данного места). И если у нас известен вес наилучшего выравнивания в 3 ячейках (см. слайд ниже), то мы можем определить вес наилучшего выравнивания в четвертой ячейке. То есть, для того, чтобы найти вес оптимального выравнивания, нам надо просмотреть m*n ячеек (количество ячеек в прямоугольной матрице MxN). Как принято говорить в информатике, это – квадратичный алгоритм. Он занимает время и объем памяти, пропорциональный квадрату длины последовательности. И вместо случайного перебора большого числа вариантов, мы решаем задачу довольно быстро.

Откуда берутся матрицы  замен? Мы берем некоторое количество выравниваний, в которое по тем  или иным причинам верим, и смотрим, как часто у нас происходят такие замены. Тогда матрица замен  является логарифмом отношения некоторых  вероятностей, которые можно оценить  как частоты.

Итак, у нас имеется  замечательный квадратичный алгоритм поиска сходства. Время решения задачи выравнивания пропорционально L1*L2. Мы сравниваем имеющуюся у нас последовательность с последовательностями в банке. L1 = размер банка = 108, а для генома человека 3х109. Сравниваемая последовательность обычно имеет размер L2=103, количество операций примерно равно 100*1011=1013.) Обычный компьютер имеет быстродействие около 109 операций в сек. На каждый шаг надо ≈102 операций. Тогда время работы равно T≈106 сек ≈ 11 дней. То есть, просеквенировав бактериальный геном из 3000 генов (приблизительно за неделю), на то, чтобы его охарактеризовать, мы потратим 11*3000 дней, то есть проанализировать дольше чем секвенировать, что, конечно, не очень хорошо.

Решением является то, что  до применения методов динамического программирования сначала выбираем правильных кандидатов для сравнения. Есть такая программа BLAST (basic local alignment search tool), которую все биологи очень любят, она почти правильная. То есть она почти всегда работает так, как требует "золотой стандарт".

Основная идея ее работы заключается в хешировании. В  самом начале мы один раз проходим по всему банку и для каждого  короткого слова с заранее  зафиксированной длиной мы запишем  список позиций, где оно встречается  в банках.

Здесь показано для слов длиной 4, в реальности слова берут  не длиной 4, как показано на рис., а  длиной 7 или 10 или 13, но принцип тот  же. В каких-то случаях "слову" соответствует три позициями, в  других – 100 позиций.

Дальше мы идем вдоль последовательности "Query" (та последовательность, которую мы хотим прогнать по банку) и выбираем очередные слова. Смотрим в таблице, где встречается это слово, вытягиваем найденные последовательности из банка и строим выравнивание их с нашей исходной последовательности. Это делается быстро, так как мы сравниваем нашу последовательность не со всеми последовательностями из банка, а только те, которые соответствуют нашему "слову" (tttgc в показанном случае). И выравнивание строим тоже не так аккуратно, как это делает алгоритм динамического программирования, а используем упрощенную схему.

Затем мы оцениваем статистическую значимость этого выравнивания –  так называемую e-value. Вообще, есть два понятия, которые очень часто встречаются в биоинформатике: e-value и р-value. Е-value – это сколько мы ожидаем увидеть совпадений с таким весом (то есть такого качества), если бы у нас наши последовательность и банк были случайными. Если они случайные, то мы ожидали бы увидеть e-1 2 совпадений.

e-value – это ожидаемое число событий, может быть больше единицы. Если e-value маленькое, то, значит, совпадение значимое, и оно несет большую биологическую информацию. Р-value – это вероятность встречи такого соответствия (не может быть больше единицы). При оценке e-value, да и вообще при любых статистических оценках, важно, какая модель лежит в основе всего этого дела. Модель, которая лежит в основе e-value, конечно же, неправильная, потому что мы не знаем правильность статистических характеристик биологических последовательностей. Е-value просто дает нам ориентир, и реально, если мы имеем e-value порядка 10^-2, то это, как правило, мусор, незначимое соответствие. Правда, есть некоторые специалисты с такой интуицией о структуре белков, которые могут работать с выравниваниями с e-value даже порядка 1. А обычно если исследователи видят e-value > 10^-3, они с этим не работают.

Есть разные модификации BLAST: BLASTp (выравнивание аминокислотных последовательностей), BLASTn (выравнивание нуклеотидных последовательностей), BLASTx (выравнивание всех возможных транслятов нашей нуклеотидной последовательности против банка аминокислотных последовательностей), TBLASTx (выравнивание всех возможных транслятов нашей нуклеотидной последовательности против всех транслятов банка нуклеотидных последовательностей). Еще нужно знать, что Nr Data Base – (non redundant) - это база, против которой обычно прогоняют BLAST, в которой нет повторяющихся последовательностей, из которой убраны дубли для того, чтобы не гонять BLAST по одним и тем же последовательностям. И score – это вес выравнивания.

А если на нашу последовательность при поиске налипло, например, не одна, а двадцать последовательностей. При  этом возникает задача написать все  эти последовательности друг под  другом, чтобы увидеть, в какой  мере они совпадают, что консервативно (устойчиво повторяется), а что  нет, и как устроена наша аминокислотная последовательность. Эта задача называется

Множественное выравнивание

Множественное выравнивание – это такой способ написания нескольких последовательностей друг под другом (может быть, с пропусками в каких-то позициях в разных последовательностях) , чтобы в каждом столбце стояли гомологичные позиции.

Для этой задачи тоже есть «золотой стандарт». Это выравнивание, которое  бы получилось, если бы мы выровняли  друг под другом последовательности, которые имеют одинаковую пространственную структуру. То есть две экспериментально установленные пространственные структуры  белка сопоставляем и отмечаем, какие  аминокислотные остатки друг под  другом встали (эти остатки соответствуют  гомологичным позициям). Это – биологически обоснованное выравнивание. Возникает  задача - найти способ (построить  алгоритм и определить параметры), который  выравнивает последовательности "золотого стандарта" (то есть последовательности, для которых пространственная структура  известно) правильно. Если такой алгоритм построен, то есть надежда, что он выровняет  последовательности с неизвестной  пространственной структурой тоже правильно.

Для решения задачи множественного выравнивания можно попробовать  написать многомерную матрицу и  построить методом динамического  программирования с просмотром многомерной  матрицы. Тогда количество вершин будет  порядка Ln , где L – длина, а n – количество последовательностей. Так как типичное количество последовательностей в семействе белков сотни, то 300 аминокислот дадут 300100 – это очень много, этот алгоритм для множественного выравнивания не подходит.

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

Такое постепенное построение выравнивание решает задачу, которую  мы не можем сформулировать математически. В биоинформатике очень часто нельзя построить математическую формулировку задачи, которую мы решаем. Поэтому формулировка задачи, которую решает алгоритм BLAST, выглядит так: мы находим то, что находит программа BLAST. Также мы не можем сказать, что мы оптимизируем при множественном выравнивании.

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

Вывод:

Конечно, в данной работе представлен лишь один из многочисленных примеров применения биоинформатики и применения динамического программирования в алгоритмах. В действительности подобных реализаций намного больше.

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