A hierarchical approach to aligning collinear regions of genomes.
BACKGROUND
As a first approximation, similarity between two long orthologous regions of genomes can be represented by a chain of local similarities. Within such a chain, pairs of successive similarities are collinear (non-conflicting), i.e. segments involved in the nth similarity precede in both sequences segments involved in the (n+1)th similarity. However, when all similarities between two long sequences are considered, usually there are many conflicts between them. Although some conflicts can be avoided by masking transposons or low-complexity sequences, selecting only those similarities that reflect orthology and, thus, belong to the evolutionarily true chain is not trivial.


RESULTS
We propose a simple, hierarchical algorithm of finding the true chain of local similarities. Starting from similarities with low P-values, we resolve each pairwise conflict by deleting a similarity with a higher P-value. This greedy approach constructs a chain of similarities faster than when a chain optimal with respect to some global criterion is sought, and makes more sense biologically.
Roytberg
Mikhail A
MA
Institute of Mathematical Problems in Biology, Pushchino, Moscow Region 142290, Russia.
Ogurtsov
Aleksey Y
AY
Shabalina
Svetlana A
SA
Kondrashov
Alexey S
AS
D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D002645:Chickens / Q000235:genetics; D017124:Conserved Sequence / Q000235:genetics; D019143:Evolution, Molecular; D017709:Fractals; D016678:Genome; D006801:Humans; D051379:Mice; D008969:Molecular Sequence Data; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software; D023741:Takifugu / Q000235:genetics