King's College London

Research portal

Extending alignments with k-mismatches and ℓ-gaps

Research output: Contribution to journalArticle

Original languageEnglish
Number of pages9
JournalJournal of Theoretical Computer Science
Volume525
DOIs
Publication statusPublished - 13 Mar 2014

King's Authors

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454