2015 | OriginalPaper | Buchkapitel
Efficient Alignment Free Sequence Comparison with Bounded Mismatches
verfasst von : Srinivas Aluru, Alberto Apostolico, Sharma V. Thankachan
Erschienen in: Research in Computational Molecular Biology
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Alignment free sequence comparison methods are attracting persistent interest, driven by data-intensive applications in genome-wide molecular taxonomy and phylogentic reconstruction. Among the methods based on substring composition, the
Average Common Substring
(
$$\mathsf {ACS}$$
) measure proposed by Burstein
et al.
(RECOMB 2005) admits a straightforward linear time sequence comparison algorithm, while yielding impressive results in multiple applications. An important direction of research is to extend the approach to permit a bounded edit/hamming distance between substrings, so as to reflect more accurately the evolutionary process. To date, however, algorithms designed to incorporate
$$k \ge 1$$
mismatches have
$$O(kn^2)$$
worst-case complexity, worse than the
$$O(n^2)$$
alignment algorithms they are meant to replace. On the other hand, accounting for mismatches does show to lead to much improved classification, while heuristics can improve practical performance. In this paper, we close the gap by presenting the first provably efficient algorithm for the
$$k$$
-mismatch average common string
(
$$\mathsf {ACS}_k$$
) problem that takes
$$O(n)$$
space and
$$O(n\log ^{k+1} n)$$
time in the worst case for any constant
$$k$$
. Our method extends the generalized suffix tree model to incorporate a carefully selected bounded set of perturbed suffixes, and can be applicable to other complex approximate sequence matching problems.