Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]