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

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

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

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

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