БЫСТРЫЙ АЛГОРИТМ ПОСТРОЕНИЯ СУПЕРДЕРЕВА ВИДОВ ПО НАБОРУ БЕЛКОВЫХ ДЕРЕВЬЕВ

摘要

Рассматривается задача построения супердерева видов по данному набору деревьев белков, генов, регу-ляторных сайтов и т.п. Доказано, что врамках традиционной постановки эта задача NP-трудная. Нами предложена новая постановка задачи: ищется супердерево, большинство клад которого представлены среди клад исходных деревьев белков. В такой постановке задача кажется биологически естественной и допускает быстрый алгоритм ее решения. Предложенный алгоритм тестировали на искусственных и биологических наборах деревьев белков, и он показал свою эффективность даже при допущении горизонтальных переносов генов. Бели горизонтальные переносы не допускаются, то математически доказывается корректность алгоритма и оценивается время его работы, которая в худшем случае имеет порядок и, где и — число деревьев генов, а— число видов в них. Наша программа построения супердерева, вместе с примерами вычислений и инструкцией для пользователя, свободно доступна на сайте http://lab6.iitp.ru/ru/super3gl/. В этой работе, а также в представленном варианте программы не рассматриваются события горизонтального переноса. Общий случай приведен в статье авторов (журнал "Проблемы передачи информации", 2011).