10:05:34
Laboratory of Mathematic methods and models in bioinformatics,
Institute for Information Transmission Problems,
Russian Academy of Sciences
A Tree-Based Method of Sequence Alignment
Annotation
In "The method description" we present an original fast algorithm of sequence alignment and its computer realization. There and in "An application example" we provide several examples of the multiple alignement of regions upstream the same gene in different genomes. An alignment is constructed with the algorithm, which uses a binary tree representation of distances between any pair of sequences from corresponding genomes (organisms). If the binary tree is unknown, it is inferred by resolving all non-binary nodes in a given non-binary tree, which is usually known. Thus, the algorithm realizes fast generation of binary trees compatible with a given non-binary tree and produces the best alignment by sampling the generated tree space. The algorithm was tested with biological data and simulations.