Chaining algorithms for multiple genome comparison
Given n  fragments from k>2 k > 2 genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in O(nlogkn) O ( n log k n ) time and O(nlogk?1n) O ( n log k ? 1 n ) space. For gap costs in the L1 L 1 -metric, we reduce the time complexity of their algorithm by a factor log 2 n log log n and the space complexity by a factor logn log n . For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor 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.
comparative genomics fragment-chaining algorithms multiple alignment range maximum query