On computing all suboptimal alignments
Journal
Information Sciences
Journal Volume
105
Journal Issue
1-4
Pages
189-207
Date Issued
1998
Author(s)
Abstract
Naor and Brutlag [D. Naor, D. Brutlag, Proceedings of the Fourth Symposium on Combinational Pattern Matching, Lecture Notes in Computer Science, 684 (1993) 179-196] proposed a new compact representation for suboptimal alignments. The kernel of that representation is a minimal directed acyclic graph (DAG) containing all suboptimal alignments. In this paper, a flexible space-saving scheme for computing such a DAG is proposed. In spite of the need for storing the DAG, these methods require very little additional working space. For two sequences of lengths M and N (M ≤ N), the general scheme runs in O(MN log(1/γ)) time and O(Mγ(M + N)) space for arbitrarily small O < γ < 1. As a consequence, the worst-case running time is O(MN log log M) using only O(N) space. A variant of the method restricts the log log M factor to affect only grid points lying between suboptimal alignments. It is also shown that a running time of O(MN) can be achieved by using only O(M1+ε + N) space for arbitrarily small constant ε > 0. To exploit the computed DAG, a variant of Aho-Corasick pattern matching machine [A.V. Aho, M.J. Corasick, Comm. ACM 18 (1975) 333-340] is employed to locate all occurrences of specified patterns, and then a path is found in the DAG that maximizes the sum of the scores of the non-overlapping patterns occurring in it. An example illustrates the utility. © 1998 Elsevier Science Inc. All rights reserved.
Type
journal article