文章基本信息

标题：Disentangled Long-Read De Bruijn Graphs via Optical Maps
本地全文：下载
作者：Bahar Alipanahi ; Leena Salmela ; Simon J. Puglisi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：88
页码：1:1-1:14
DOI：10.4230/LIPIcs.WABI.2017.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：While long reads produced by third-generation sequencing technology from, e.g, Pacific Biosciences have been shown to increase the quality of draft genomes in repetitive regions, fundamental computational challenges remain in overcoming their high error rate and assembling them efficiently. In this paper we show that the de Bruijn graph built on the long reads can be efficiently and substantially disentangled using optical mapping data as auxiliary information. Fundamental to our approach is the use of the positional de Bruijn graph and a succinct data structure for constructing and traversing this graph. Our experimental results show that over 97.7% of directed cycles have been removed from the resulting positional de Bruijn graph as compared to its non-positional counterpart. Our results thus indicate that disentangling the de Bruijn graph using positional information is a promising direction for developing a simple and efficient assembly algorithm for long reads.
关键词：Positional de Bruijn graph; Genome Assembly; Long Read Data; Optical maps