Chaining algorithms for multiple genome comparison

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(nlogkn) time and O(nlogk−1n) space. For gap costs in the L1-metric, we reduce the time complexity of their algorithm by a factor log2nloglogn and the space complexity by a factor logn. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor lognloglogn. 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.