Sequence comparison with concave weighting functions (Q1101364)

We consider efficient methods for computing a difference metric between two sequences of symbols, where the cost of an operation to insert or delete a block of symbols is a concave function of the block's length. Alternatively, sequences can be optimally aligned when gap penalties are a concave function of the gap length. Two algorithms based on the `candidate list paradigm' first used by \textit{M. S. Waterman} [J. theor. Biol. 108, 333-337 (1984)] are presented. The first computes significantly more parsimonious candidate lists than Waterman's method. The second method refines the first to the point of guaranteeing \(O(N^ 2lg N)\) worst-case time complexity, and under certain conditions \(O(N^ 2).\) Experimental data show how various properties of the comparison problem affect the methods' relative performance. A number of extensions are discussed, among them a technique for constructing optimal alignments in O(N) space in expectation. This variation gives a practical method for comparing long amino sequences on a small computer.