Разработка алгоритмов для вычислительной биологии: различия между версиями

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

На данный момент практически любая модель видообразования и геномной эволюции, применяемая в филогенетической реконструкции, требует решения NP-трудных задач оптимизации. Наиболее широко применяются три основных класса методов. Эвристические методы (естественное следствие NP-трудности задачи) работают быстро, но не могут обеспечить гарантий качества и могут даже не обладать точно определенными критериями оптимизации – примером может служить популярный эвристический метод связывания ближайших соседей [9]. Методы оптимизации на основе критерия максимальной экономичности (maximum parsimony, MP) [4] стремятся обнаружить филогению с минимальным совокупным количеством изменений, необходимых для объяснения современных данных. И, наконец, методы оптимизации на основе критерия максимального правдоподобия (maximum likelihood, ML) [5] стремятся обнаружить филогению, которая с наибольшей вероятностью послужила основой для современных данных.

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

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

В качестве иллюстрации вкратце опишем высокопроизводительный пакет программ GRAPPA (анализ перестановок генома при помощи подхода на базе экономичности и других филогенетических алгоритмов, Genome Rearrangement Analysis through Parsimony and other Phylogenetic Algorithms), разработанного Бадером и коллегами. GRAPPA расширяет алгоритм поиска точек разрывов Санкоффа и Бланшетта [10] на более информативную с биологической точки зрения инверсионную филогению, а его оптимизированный код позволяет использовать параллельные системы с распределенной и совместно используемой памятью (подробнее см. в [1, 2, 6, 7, 8, 11]). В работе [3] Бадер и коллеги предложили первый алгоритм с линейным временем выполнения и быструю реализацию для вычисления расстояния инверсии между двумя подписанными перестановками. При выполнении на кластере IBM Linux с 512 процессорами в среде Myrinet алгоритм GRAPPA обеспечил ускорение в 512 раз (линейное ускорение относительно числа процессоров). Полный анализ точек разрывов (использующий более требовательный алгоритм поиска расстояния инверсии вместо расстояния между точками разрывов) для 13 геномов из набора данных о семействе колокольчиковых (Campanulaceae) в октябре 2000 года был выполнен менее чем за 1,5 часа – в миллион раз быстрее по сравнению с первоначальной реализацией. Новая версия характеризуется значительно улучшенными границами и применением новых методов поправки на расстояние – и обеспечивает ускорение более чем в миллиард раз на том же наборе данных. Это ускорение достигается GRAPPA за счет сочетания параллелизма и использования высокоэффективных алгоритмов. На подобное грандиозное ускорение не всегда можно рассчитывать, однако многие алгоритмические подходы, используемые сегодня биологическими, фармацевтическими и медицинскими сообществами, могут получить значительные преимущества благодаря применению подобных высокопроизводительных техник и платформ.

* [[Эффективные методы множественного выравнивания последовательностей с гарантированными границами погрешности]]

* [[Локальное выравнивание (с аффинными штрафами за делецию)]]

* [[Локальное выравнивание (с вогнутыми штрафами за делецию)]]

* [[Сортировка подписанных перестановок при помощи обращений (расстояние обращения)]]

* [[Сортировка подписанных перестановок при помощи обращений (последовательность обращений)]]

* [[Сортировка при помощи перестановок и обращений (коэффициент аппроксимации 1,5)]]