License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2018.12
URN: urn:nbn:de:0030-drops-93143
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9314/
Go to the corresponding LIPIcs Volume Portal

Muggli, Martin D. ; Puglisi, Simon J. ; Boucher, Christina

A Succinct Solution to Rmap Alignment

pdf-format:
LIPIcs-WABI-2018-12.pdf (0.6 MB)

Abstract

We present Kohdista, which is an index-based algorithm for finding pairwise alignments between single molecule maps (Rmaps). The novelty of our approach is the formulation of the alignment problem as automaton path matching, and the application of modern index-based data structures. In particular, we combine the use of the Generalized Compressed Suffix Array (GCSA) index with the wavelet tree in order to build Kohdista. We validate Kohdista on simulated E. coli data, showing the approach successfully finds alignments between Rmaps simulated from overlapping genomic regions. Lastly, we demonstrate Kohdista is the only method that is capable of finding a significant number of high quality pairwise Rmap alignments for large eukaryote organisms in reasonable time. Kohdista is available at https://github.com/mmuggli/KOHDISTA/.

BibTeX - Entry

@InProceedings{muggli_et_al:LIPIcs:2018:9314,
  author =	{Martin D. Muggli and Simon J. Puglisi and Christina Boucher},
  title =	{{A Succinct Solution to Rmap Alignment}},
  booktitle =	{18th International Workshop on Algorithms in  Bioinformatics (WABI 2018)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Laxmi Parida and Esko Ukkonen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9314},
  URN =		{urn:nbn:de:0030-drops-93143},
  doi =		{10.4230/LIPIcs.WABI.2018.12},
  annote =	{Keywords: Optical mapping, index based data structures, FM-index, graph algorithms}
}

Keywords: Optical mapping, index based data structures, FM-index, graph algorithms
Collection: 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Issue Date: 2018
Date of publication: 02.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI