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

== Ключевые слова и синонимы ==
Высокоэффективные подходы в вычислительной биологии

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


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


Алгоритмы для решения задач вычислительной биологии нередко требуют применения техник параллельной обработки в силу огромных объемов данных и вычислений. Многие задачи используют алгоритмы с полиномиальным временем выполнения (например, сравнение «всех со всеми»), однако работают очень долго из-за большого количества элементов входных данных; примерами таких задач могут служить сборка полного генома или сравнение всех данных нуклеотидной последовательности гена со всеми. Другие задачи требуют высокой вычислительной мощности из-за присущей алгоритмам сложности; к ним можно отнести укладку белка и реконструкцию истории эволюции на основе молекулярных данных; эти задачи являются NP-трудными или еще более сложными и нередко нуждаются в аппроксимациях, также далеко не простых.

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


На данный момент практически любая модель видообразования и геномной эволюции, применяемая в филогенетической реконструкции, требует решения 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 за счет сочетания параллелизма и высокоэффективных алгоритмов. На подобное грандиозное ускорение не всегда можно рассчитывать, однако многие алгоритмические подходы, используемые сегодня биологическими, фармацевтическими и медицинскими сообществами, могут получить значительные преимущества благодаря применению подобных высокопроизводительных техник и платформ.


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

== См. также ==
* [[Реконструкция филогенеза на основе расстояния (быстрая сходимость)]]
* [[Реконструкция филогенеза на основе расстояния (оптимальный радиус)]]
* [[Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок]]
* [[Разработка высокоэффективных алгоритмов для крупномасштабных задач]]
* [[Локальное выравнивание (с аффинными штрафами за гэп)]]
* [[Локальное выравнивание (с вогнутыми штрафами за гэп)]]
* [[Многолокусная ПЦР для сокращения разрывов (при сборке полного генома)]]
* [[Масс-спектрометрическое de novo секвенирование пептидов]]
* [[Гаплотипирование совершенного филогенеза]]
* [[Построение филогенетического дерева из матрицы расстояний]]
* [[Реконструкция филогении]]
* [[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)]]
* [[Сортировка перестановок со знаками при помощи обращений (последовательность обращений)]]
* [[Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5)]]
* [[Максимальная экономичность для подстрок]]

== Литература ==
1.	Bader, D.A., Moret, B.M.E., Warnow, T., Wyman, S.K., Yan, M.: High-performance algorithm engineering for gene-order phylogenies. In: DIMACS Workshop on Whole Genome Comparison, Rutgers University, Piscataway, NJ (2001)

2.	Bader, D.A., Moret, B.M.E., Vawter, L.: Industrial applications of high-performance computing for phylogeny reconstruction. In: Siegel, H.J. (ed.) Proc. SPIE Commercial Applications for High-Performance Computing, vol.4528, pp. 159-168, Denver, CO (2001)

3.	Bader, D.A., Moret, B.M.E., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J. Comp. Biol. 8(5), 483^91 (2001)

4.	Farris, J.S.: The logical basis of phylogenetic analysis. In: Platnick, N.I., Funk, V.A. (eds.) Advances in Cladistics, pp. 1-36. Columbia Univ. Press, New York (1983)

5.	Felsenstein, J.: Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 17, 368-376 (1981)

6.	Moret, B.M.E., Bader, D.A., Warnow, T., Wyman, S.K., Yan, M.: GRAPPA: a highperformance computational tool for phylogeny reconstruction from gene-order data. In: Proc. Botany, Albuquerque, August 2001

7.	Moret, B.M.E., Bader, D.A., Warnow, T.: High-performance algorithm engineering for computational phylogenetics. J. Supercomp. 22,99-111 (2002) Special issue on the best papers from ICCS'01

8.	Moret, B.M.E., Wyman, S., Bader, D.A., Warnow, T., Yan, M.: A new implementation and detailed study of breakpoint analysis. In: Proc. 6th Pacific Symp. Biocomputing (PSB 2001), pp. 583-594, Hawaii, January 2001

9.	Saitou, N., Nei, M.: The neighbor-joining method: A new method for reconstruction of phylogenetic trees. Mol. Biol. Evol. 4,406-425 (1987)

10.	Sankoff, D., Blanchette, M.: Multiple genome rearrangement and breakpoint phylogeny. J. Comp. Biol. 5, 555-570 (1998)

11.	Yan, M.: High Performance Algorithms for Phylogeny Reconstruction with Maximum Parsimony. Ph.D. thesis, Electrical and Computer Engineering Department, University of New Mexico, Albuquerque, January 2004