Abstract | ||
---|---|---|
Motivation: 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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1093/bioinformatics/18.12.1673 | BIOINFORMATICS |
Field | DocType | Volume |
Software tool,Genome,Pairwise comparison,Computer science,Hierarchical algorithm,Bioinformatics | Journal | 18 |
Issue | ISSN | Citations |
12.0 | 1367-4803 | 4 |
PageRank | References | Authors |
0.83 | 10 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mikhail A. Roytberg | 1 | 114 | 54.66 |
Aleksey Y. Ogurtsov | 2 | 41 | 4.42 |
S A Shabalina | 3 | 42 | 5.55 |
A S Kondrashov | 4 | 13 | 3.32 |