Алгоритм сравнения филогенетических деревьев, основанный на треугольных матрицах

Cтудентка

Московский государственный университет имени ,

физический факультет, Москва, Россия

E-mail: mariaalzh@mail.ru

Проблема сравнения топологии филогенетических деревьев актуальна для определения горизонтально перенесенных генов. В идеале нужно определить минимальное число трансформаций, необходимое совершить, чтобы получить из одной топологии дерева другую. Данная метрика сравнения филогенетических деревьев называется SPR-расстоянием (Subtree Pruning and Regrafting). Было показано, что задача нахождения SPR-расстояния принадлежит классу NP трудных задач [2]. Для преодоления вычислительной трудности в практике используются другие подходы, как, например, расстояния, основанные на спектре бипартиций [4] или квартетов [3], или метод, основанный на методах максимального правдоподобия - AU-test [1]. Каждый метод имеет свои ограничения и недостатки. Все методы имеют существенные ограничения на размер дерева. Здесь предлагается метод сравнения филогенетических деревьев, основанный на треугольных матрицах, в которых элементы матрицы являются нодальными расстояниями между листьями. При таком подходе, расстояния между деревьями может вычисляется с помощью алгебраических операций над матрицами. Метод был протестирован на семействах ортологов бактерий и архей.

Список литературы

1.  Shimodaira, H. (2002) An approximately unbiased test of phylogenetic tree selection. Syst Biol 51, 492–508.

2.  Bordewich M, Semple C. On the computational complexity of the rooted subtree prune and regraft distance. binatorics 2004; 8:409-423.

3.  Mao F, Williams D, Zhaxybayeva O, Poptsova M, Lapierre P, Gogarten JP, Xu Y. (2012) Quartet decomposition server: a platform for analyzing phylogenetic trees// BMC Bioinformatics. 2012 Jun 7;13:123.

4.  Hamel L, Nahar N, Popstova MS, Zhaxybayeva O, Gogarten JP (2008) Unsupervised learning in detection of gene transfer// J. Biomed Biotech 2008