文章基本信息

标题：A Succinct Solution to Rmap Alignment
本地全文：下载
作者：Martin D. Muggli ; Simon J. Puglisi ; Christina Boucher 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：113
页码：1-16
DOI：10.4230/LIPIcs.WABI.2018.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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/.
关键词：Optical mapping; index based data structures; FM-index; graph algorithms