4551
правка
Разработка алгоритмов для вычислительной биологии: различия между версиями
Перейти к навигации
Перейти к поиску
Разработка алгоритмов для вычислительной биологии (посмотреть исходный код)
Версия от 10:46, 9 января 2019
, 9 января 2019→Экспериментальные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Высокоэффективные подходы в вычислительной биологии == По…») |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
В качестве иллюстрации вкратце опишем высокопроизводительный пакет программ GRAPPA (анализ перестановок генома при помощи подхода на базе экономичности и других филогенетических алгоритмов, Genome Rearrangement Analysis through Parsimony and other Phylogenetic Algorithms), разработанного Бадером и коллегами. GRAPPA расширяет алгоритм поиска точек разрывов Санкоффа и Бланшетта [10] на более информативную с биологической точки зрения инверсионную филогению, а его оптимизированный код позволяет использовать параллельные системы с распределенной и совместно используемой памятью (подробнее см. в [1, 2, 6, 7, 8, 11]). В работе [ ] Бадер и коллеги предложили первый алгоритм с линейным временем выполнения и быструю реализацию для вычисления расстояния инверсии между двумя подписанными перестановками. При выполнении на кластере 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 | |||