A Graph-Theoretic Barcode Ordering Model for Linked-Reads - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2020

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.
Fichier principal
Vignette du fichier
LIPIcs-WABI-2020-11.pdf (1.78 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-03008334 , version 1 (17-11-2020)

Identifiers

Cite

Yoann Dufresne, Chen Sun, Pierre Marijon, Dominique Lavenier, Cedric Chauve, et al.. A Graph-Theoretic Barcode Ordering Model for Linked-Reads. WABI 2020 - 20th Workshop on Algorithms in Bioinformatics, Sep 2020, Pisa, Italy. pp.11 - 12, ⟨10.4230/LIPIcs.WABI.2020.11⟩. ⟨hal-03008334⟩
181 View
99 Download

Altmetric

Share

Gmail Facebook X LinkedIn More