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

Текст из файла (страница 3)

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

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

Лучшим считается то, которое имеет наименьшую цену. Например, при цене замены 1 и цене вставки/удаления 3, лучшими в примере во врезке 2 будут третье и четвертое выравнивания, а при цене замены 10 и той же цене вставки/удаления, лучшим будет пятое.

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

Поэтому вместо «цены замены символа» в схеме редактирующего расстояния при сравнении белков используется весовая матрица замен, где каждой паре символов соответствует вес (положительный - для похожих, отрицательный для непохожих), а выравниванию в целом - вес W=R-G, где R - суммарный вес сопоставлений символов (в соответствии с выбранной весовой матрицей замен), G - суммарный штраф за удаления и вставки символов. Таким образом, оптимальное выравнивание - это выравнивание, имеющее наибольший вес (в то время как цена требовалась наименьшая). Например, пусть вес совпадения для гласных букв +2, вес совпадения для согласных букв +1, вес сопоставления двух различных гласных или двух различных согласных -1, вес сопоставления гласной и согласной -2. Далее, пусть штраф за удаление или вставку символа -5. Тогда, например, третье выравнивание имеет вес -3, а четвертое - +1. Таким образом, оптимальное выравнивание слов ПОДБЕРЕЗОВИК и ПОДОСИНОВИК (при выбранных матрице замен и штрафе за удаление/вставку) - четвертое. Переход от минимизации цены к максимизации качества, - это не только технический трюк. На языке максимизации качества естественно ставится задача о поиске оптимального локального сходства. Эта задача соответствует сравнению двух белков, которые в ходе эволюции стали совсем непохожи - везде, кроме относительно короткого участка.

Алгоритм построения оптимального выравнивания основан на методе динамического программирования, введенном в широкую практику Ричардом Беллманом в 1957. Идея метода состоит в следующем: чтобы решить основную задачу, нужно придумать множество промежуточных и последовательно их решить (в каком порядке - отдельный вопрос). При этом очередная промежуточная задача должна «легко» решаться, исходя из уже известных решений ранее рассмотренных задач. Множество промежуточных задач удобно представлять в виде ориентированного ациклического графа. Его вершины соответствуют промежуточным задачам, а ребра указывают на то, результаты решений каких промежуточных задач используются для основной. Таким образом, исходная задача сводится к поиску оптимального пути в графе ² (подробнее о методе динамического программирования см. книгу Ахо, Хопкрофта и Ульмана, а также статью Finkelstein A.V., Roytberg M.A. Computation of biopolymers: a general approach to different problems. Biosystems.1993; 30 (1-3): 1-19.). Аналогично можно переформулировать различные варианты задач выравнивания, предсказания вторичной структуры РНК и белков, поиска белок-кодирующих областей ДНК и других важных проблем биоинформатики.

При построении оптимального выравнивания (мы рассматриваем простейший случай, когда удаление и вставка отдельных символов штрафуются независимо) промежуточные задачи - это построение оптимальных выравниваний начальных фрагментов исходных последовательностей. При этом задачи нужно решать в порядке возрастания длин фрагментов. Граф зависимости между промежуточными решениями для сравнения слов «ПАПКА» и «ПАПАХА», а также последовательность промежуточных шагов, приводящих к оптимальному выравниванию, показаны на рис. 2.

Рис. 2.

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

Врезка 1
Врезка 2
Врезка 3: Алгоритм оптимального выравнивания (набросок)

1 (обратно к тексту) - Последняя монография - Pavel A. Pevzner. Computational Molecular Biology. An Algorithmic Approach. The MIT Press. Cambridge, MA, 2000, из книг на русском языке укажем М. С. Уотермен (ред). Математические методы для анализа последовательностей ДНК.-М.: Мир, 1999.
2 (обратно к тексту) - Иногда (например, в упоминавшейся задаче о построении оптимальной вторичной структуры РНК) приходится рассматривать не графы, а гиперграфы. Гиперграф отличается от графа тем, что вместо ребер на множестве вершин задаются гиперребра. Ребро в (ориентированном) графе сопоставляет начальной вершине одну конечную вершину. Гиперребро сопоставляет начальной вершине множество вершин (не обязательно одноэлементное). Аналогом пути в гиперграфе является гиперпуть - объект, похожий на дерево.

С точки зрения алгоритма построения оптимального выравнивания введение весовых матриц ничего не меняет. Однако оказывается, что нельзя рассматривать удаление одного символа как отдельное эволюционное событие. Вес нужно приписывать удалению целого фрагмента, и этот вес должен зависеть от длины фрагмента. Ограничения на выбор функции G(L) штрафов за удаление фрагментов (L - длина удаляемого фрагмента) влияют на эффективность построения оптимального выравнивания. В простейшем случае посимвольных замен (этот случай соответствует функции G(L)=k•L, где k - штраф за удаление одного символа) время работы квадратично зависит от длины сравниваемых слов (считаем, что их длины примерно равны), а в случае допустимости произвольных штрафных функций порядок роста времени работы соответствующего алгоритма - кубический. Компьютерные эксперименты показали, что разумным компромиссом служат линейные функции вида G(L)=k•L+s, где s - штраф за начало удаления/вставки, где k и L имеют тот же смысл, что и раньше. Для таких функций можно построить квадратичный по времени работы алгоритм построения оптимального выравнивания (хотя и с большей константой пропорциональности).

Алгоритм оптимального выравнивания (набросок)

Пусть нам нужно найти оптимальное выравнивание последовательностей U=Xa и W=Yb (здесь a - последняя буква U, b - последняя буква W, последовательности X и Y - получаются соответственно из U и W отбрасыванием последней буквы. Для оптимального выравнивания возможны ровно три альтернативы:

• последние буквы слов U и W сопоставлены друг другу;

• последняя буква слова U удалена, последняя буква слова W - нет;

• последняя буква слова W удалена, последняя буква слова U - нет.

В первом случае вес оптимального выравнивания равен

S₁ = S(X, Y)+m(a, b).

Здесь S(X, Y) - вес оптимального выравнивания последовательностей X и Y (оно уже построено ранее, т. к. пара (X, Y) рассмотрена до текущей пары (U, W)), m(a, b) - вес сопоставления символов a и b.

Во втором и третьем случае аналогично получаем формулы:

S₂ = S(X, Yb)+g,

S₃ = S(Xa, Y)+g.

Здесь g - штраф за удаление символа, S(X, Yb) и S(Xa, Y) - веса оптимальных выравниваний для пар последовательностей (X и Yb = W) и (Xa=U и Y) соответственно. Оптимальные выравнивания для этих пар последовательностей тоже построены ранее. Таким образом, чтобы найти вес S(U, W) оптимального выравнивания последовательностей U и W и само это выравнивание, достаточно найти наибольшее из чисел S₁ , S₂ , S₃. Очевидно, каждое из этих чисел можно вычислить за конечное (не зависящее от длин исходных последовательностей) время. Поэтому общее время построения оптимального выравнивания двух последовательностей пропорционально количеству промежуточных задач, т. е. произведению длин этих последовательностей.

Биочипы как пример индустриальной биологии

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

Характеристики

Список файлов реферата