Monge properties of sequence alignment
Alignment is an important sequence comparison measure. Algorithms that compute alignments have a wide range of applications, namely in bioinformatic tools. Alignments can be computed as maximum scoring paths in Alignment DAGs. In this paper we study the properties of matrices that contain alignment scores between a string and all the sub-strings of another string. We focus on the fact that these matrices have the Monge property and are sparse in some sense. Related studies were recently presented for HSM and DIST matrices, leading to O(n log n) procedure for multiplying those matrices, where O(n) bounds the sizes of the strings. Our results strictly generalize previous solutions. We measure the sparseness of the matrices with variable delta and present an algorithm for matrix multiplication in O((n + delta) log(3)(n + delta)) time, which we improve to O((n + delta) log(2)(n + delta)), within the same space. We discuss applications of this algorithm, namely fully incremental alignment and alignment update. We study, experimentally, the performance of the methods we propose. (C) 2011 Elsevier B.V. All rights reserved.
monge property alignment matrix multiplication cyclic strings edit distance longest common subsequence computational complexity string matching incremental string comparison