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(nlogn) 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 δ and present an algorithm for matrix multiplication in O((n+δ)log3(n+δ)) time, which we improve to O((n+δ)log2(n+δ)), 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.