@article{4412,
  author = {Yoann Dufresne, Chen Sun, Pierre Marijon, Dominique Lavenier, Cedric Chauve, Rayan Chikhi},
  title = {Generating Heuristic Estimates using Intersection Graphs},
  journal = {Progress in Computing Applications},
  year = {2025},
  volume = {14},
  number = {1},
  doi = {https://doi.org/10.6025/pca/2025/14/1/19-37},
  url = {https://www.dline.info/pca/fulltext/v14n1/pcav14n1_2.pdf},
  abstract = {When dealing with a collection of intervals on the real number line, an interval graph represents these
intervals as nodes and their overlaps as edges. Merging pairs of nodes in an interval graph leads to forming
a multiple-interval graph. We seek to answer some critical questions with access only to the nodes and edgesof this multiple-interval graph without the original intervals. Is it possible to determine how many intervals
are associated with each node? Can we find a path through the nodes of the multiple-interval graph that
reflects the sequence of the original intervals? These inquiries are closely tied to linked-read DNA sequencing,
where long molecules are labeled with barcodes, and their intersection graph creates an interval graph.
Each barcode might represent several molecules, complicating further analysis and correlating with the
identification of nodes in the respective interval graph. Addressing these graph-theoretic challenges would
enhance the analysis of linked-reads sequencing data by allowing for the conceptual distinction of barcodes
into individual molecules and providing a framework for accurately reconstructing the genome through the
arrangement of these molecules. In this context, we introduce a framework that accepts any given intersection
graph (like the overlap graph of barcodes) and produces a heuristic estimate of the arrangement of the
original intervals.},
}