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(nlog^kn) time and O(nlog^k−1n) space. For gap costs in the L₁-metric, we reduce the time complexity of their algorithm by a factor 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 . 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.