Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1110.68541
Abouelhoda, Mohamed Ibrahim; Ohlebusch, Enno
Chaining algorithms for multiple genome comparison.
(English)
[J] J. Discrete Algorithms 3, No. 2-4, 321-341 (2005). ISSN 1570-8667

Summary: Given $n$ fragments from $k>2$ genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in $O(n\log^kn)$ time and $O(n\log^{k-1}n)$ space. For gap costs in the $L_1$-metric, we reduce the time complexity of their algorithm by a factor $\frac {\log^2n}{\log\log n}$ and the space complexity by a factor $\log n$. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor $\frac{\log n}{\log\log n}$. A variant of our algorithm finds all significant local chains of colinear non-overlapping fragments. These chaining algorithms can be used in a variety of problems in comparative genomics: the computation of global alignments of complete genomes, the identification of regions of similarity (candidate regions of conserved synteny), the detection of genome rearrangements, and exon prediction.
MSC 2000:
*68W05 Nonnumerical algorithms
92C37 Cell biology
92D10 Genetics

Keywords: fragment-chaining algorithms; multiple alignment; range maximum query

Highlights
Master Server