Выравнивание последовательностей на основе дерева
Предложены алгоритм и компьютерная программа для построения выравнивания данного набора последовательностей. В приводимых примерах эти последовательности интерпретируются как участки, расположенные в геномах различных организмов перед одним и тем же геном. Выравнивание строится с помощью оригинального быстрого алгоритма, использующего бинарное дерево, которое указывает на степень родства любых двух данных последовательностей (фактически — на степень родства соответствующих организмов). Если бинарное дерево неизвестно, то алгоритм получает его путём разрешения всех небинарных вершин в данном небинарном дереве, которое обычно уже известно в отличие от бинарного. Таким образом, алгоритм включает быстрый способ порождения без повторений всех бинарных деревьев, топологически совместимых с данным небинарным деревом, и, перебирая их все, он выдаёт выравнивание наилучшего качества. Алгоритм тестировался на искусственных и биологических данных.