Lab.6 IITP RAS logo
29/03/24
08:28:31

Лаборатория математических методов и моделей в биоинформатике
Института проблем передачи информации им. А.А. Харкевича
Российской академии наук

« back

Выравнивание последовательностей на основе дерева

Аннотация

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

Описание метода (PDF)

Программа с кратким описанием « back