Extending alignments with k-mismatches and ℓ-gaps

Carl Barton; Costas Iliopoulos; Inbok Lee; Laurent Mouchard; Kunsoo Park; Solon Pissis

doi:10.1016/j.tcs.2013.06.012

Extending alignments with k-mismatches and ℓ-gaps

Carl Barton, Costas Iliopoulos, Inbok Lee, Laurent Mouchard, Kunsoo Park, Solon Pissis

Informatics

Research output: Contribution to journal › Article › peer-review

Abstract

Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al., 2011). The authors considered the problem of extending an alignment under the Hamming distance model by also allowing the insertion of a single gap; and presented a Θ(mβ)-time algorithm to solve it, where m is the length of the shortest sequence to be extended, and β is the maximum allowed length of the single gap. Very recently, it was shown (Flouri et al., 2012) that this problem is strongly and directly motivated by the next-generation re-sequencing application: aligning tens of millions of short DNA sequences against a reference genome. In this article, we consider an extension of this problem: extending an alignment with k-mismatches and two gaps ; and present a Θ(mβ)-time algorithm to solve it. This extension is proved to be fundamental in the next-generation re-sequencing application (Alachiotis et al., 2012). In addition, we present a generalisation of our solution to solve the problem of extending an alignment with k-mismatches and ℓ-gaps in time Θ(mβℓ). The presented solutions work provided that all gaps in the alignment must occur in one of the two sequences.

Original language	English
Number of pages	9
Journal	Journal of Theoretical Computer Science
Volume	525
DOIs	https://doi.org/10.1016/j.tcs.2013.06.012
Publication status	Published - 13 Mar 2014

Access to Document

10.1016/j.tcs.2013.06.012

Cite this

@article{7db386e26188415c8ab27e525c79be21,

title = "Extending alignments with k-mismatches and ℓ-gaps",

abstract = "Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al., 2011). The authors considered the problem of extending an alignment under the Hamming distance model by also allowing the insertion of a single gap; and presented a Θ(mβ)-time algorithm to solve it, where m is the length of the shortest sequence to be extended, and β is the maximum allowed length of the single gap. Very recently, it was shown (Flouri et al., 2012) that this problem is strongly and directly motivated by the next-generation re-sequencing application: aligning tens of millions of short DNA sequences against a reference genome. In this article, we consider an extension of this problem: extending an alignment with k-mismatches and two gaps ; and present a Θ(mβ)-time algorithm to solve it. This extension is proved to be fundamental in the next-generation re-sequencing application (Alachiotis et al., 2012). In addition, we present a generalisation of our solution to solve the problem of extending an alignment with k-mismatches and ℓ-gaps in time Θ(mβℓ). The presented solutions work provided that all gaps in the alignment must occur in one of the two sequences.",

author = "Carl Barton and Costas Iliopoulos and Inbok Lee and Laurent Mouchard and Kunsoo Park and Solon Pissis",

year = "2014",

month = mar,

day = "13",

doi = "10.1016/j.tcs.2013.06.012",

language = "English",

volume = "525",

journal = "Journal of Theoretical Computer Science",

}

TY - JOUR

T1 - Extending alignments with k-mismatches and ℓ-gaps

AU - Barton, Carl

AU - Iliopoulos, Costas

AU - Lee, Inbok

AU - Mouchard, Laurent

AU - Park, Kunsoo

AU - Pissis, Solon

PY - 2014/3/13

Y1 - 2014/3/13

N2 - Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al., 2011). The authors considered the problem of extending an alignment under the Hamming distance model by also allowing the insertion of a single gap; and presented a Θ(mβ)-time algorithm to solve it, where m is the length of the shortest sequence to be extended, and β is the maximum allowed length of the single gap. Very recently, it was shown (Flouri et al., 2012) that this problem is strongly and directly motivated by the next-generation re-sequencing application: aligning tens of millions of short DNA sequences against a reference genome. In this article, we consider an extension of this problem: extending an alignment with k-mismatches and two gaps ; and present a Θ(mβ)-time algorithm to solve it. This extension is proved to be fundamental in the next-generation re-sequencing application (Alachiotis et al., 2012). In addition, we present a generalisation of our solution to solve the problem of extending an alignment with k-mismatches and ℓ-gaps in time Θ(mβℓ). The presented solutions work provided that all gaps in the alignment must occur in one of the two sequences.

AB - Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al., 2011). The authors considered the problem of extending an alignment under the Hamming distance model by also allowing the insertion of a single gap; and presented a Θ(mβ)-time algorithm to solve it, where m is the length of the shortest sequence to be extended, and β is the maximum allowed length of the single gap. Very recently, it was shown (Flouri et al., 2012) that this problem is strongly and directly motivated by the next-generation re-sequencing application: aligning tens of millions of short DNA sequences against a reference genome. In this article, we consider an extension of this problem: extending an alignment with k-mismatches and two gaps ; and present a Θ(mβ)-time algorithm to solve it. This extension is proved to be fundamental in the next-generation re-sequencing application (Alachiotis et al., 2012). In addition, we present a generalisation of our solution to solve the problem of extending an alignment with k-mismatches and ℓ-gaps in time Θ(mβℓ). The presented solutions work provided that all gaps in the alignment must occur in one of the two sequences.

U2 - 10.1016/j.tcs.2013.06.012

DO - 10.1016/j.tcs.2013.06.012

M3 - Article

VL - 525

JO - Journal of Theoretical Computer Science

JF - Journal of Theoretical Computer Science

ER -

Extending alignments with k-mismatches and ℓ-gaps

Abstract

Access to Document

Fingerprint

Cite this