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