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.2020.11
URN: urn:nbn:de:0030-drops-128001
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12800/
Dufresne, Yoann ;
Sun, Chen ;
Marijon, Pierre ;
Lavenier, Dominique ;
Chauve, Cedric ;
Chikhi, Rayan
A Graph-Theoretic Barcode Ordering Model for Linked-Reads
Abstract
Considering a set of intervals on the real line, an interval graph records these intervals as nodes and their intersections as edges. Identifying (i.e. merging) pairs of nodes in an interval graph results in a multiple-interval graph. Given only the nodes and the edges of the multiple-interval graph without knowing the underlying intervals, we are interested in the following questions. Can one determine how many intervals correspond to each node? Can one compute a walk over the multiple-interval graph nodes that reflects the ordering of the original intervals? These questions are closely related to linked-read DNA sequencing, where barcodes are assigned to long molecules whose intersection graph forms an interval graph. Each barcode may correspond to multiple molecules, which complicates downstream analysis, and corresponds to the identification of nodes of the corresponding interval graph. Resolving the above graph-theoretic problems would facilitate analyses of linked-reads sequencing data, through enabling the conceptual separation of barcodes into molecules and providing, through the molecules order, a skeleton for accurately assembling the genome. Here, we propose a framework that takes as input an arbitrary intersection graph (such as an overlap graph of barcodes) and constructs a heuristic approximation of the ordering of the original intervals.
BibTeX - Entry
@InProceedings{dufresne_et_al:LIPIcs:2020:12800,
author = {Yoann Dufresne and Chen Sun and Pierre Marijon and Dominique Lavenier and Cedric Chauve and Rayan Chikhi},
title = {{A Graph-Theoretic Barcode Ordering Model for Linked-Reads}},
booktitle = {20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
pages = {11:1--11:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-161-0},
ISSN = {1868-8969},
year = {2020},
volume = {172},
editor = {Carl Kingsford and Nadia Pisanti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12800},
URN = {urn:nbn:de:0030-drops-128001},
doi = {10.4230/LIPIcs.WABI.2020.11},
annote = {Keywords: DNA sequencing, graph algorithms, linked-reads, interval graphs, cliques}
}
