GapsMis: Flexible sequence alignment with a bounded number of gaps

Carl Barton, Tomáš Flouri, Costas S. Iliopoulos, Solon P. Pissis

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Motivation: Recent developments in next-generation sequencing technologies have renewed interest in pairwise sequence alignment techniques, particularly so for the application of re-sequencing-the assembly of a genome directed by a reference sequence. After the fast alignment between a factor of the reference sequence and the high-quality fragment of a short read, an important problem is to find the best possible alignment between a succeeding factor of the reference sequence and the remaining low-quality part of the read; allowing a number of mismatches and the insertion of gaps in the alignment. Results: We present GapsMis, a tool for pairwise global and semi-global sequence alignment with a variable, but bounded, number of gaps. It is based on a new algorithm, which computes a different version of the traditional dynamic programming matrix. Millions of pairwise sequence alignments, performed under realistic conditions based on the properties of real full-length genomes, show that GapsMis can increase the accuracy of extending short-read alignments end-to-end compared to more traditional approaches.

Original languageEnglish
Title of host publication2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
Pages402-411
Number of pages10
DOIs
Publication statusPublished - 28 Nov 2013
Externally publishedYes
Event2013 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013 - Wshington, DC, United States
Duration: 22 Sep 201325 Sep 2013

Publication series

Name2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013

Conference

Conference2013 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
CountryUnited States
CityWshington, DC
Period22/09/1325/09/13

Keywords

  • Gaps
  • Pairwise sequence alignment
  • Short-read mapping

Fingerprint

Dive into the research topics of 'GapsMis: Flexible sequence alignment with a bounded number of gaps'. Together they form a unique fingerprint.

Cite this