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

Материал из WEGA

Ключевые слова и синонимы

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

Постановка задачи

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


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

См. также

Литература

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

Источник — http://pco.iis.nsk.su/wega/index.php?title=Разработка_алгоритмов_для_вычислительной_биологии&oldid=15235