2026-07-20T05:09:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11047 2024-03-06T10:47:28Z ddc:004 open_access

Validating Paired-End Read Alignments in Sequence Graphs Jain, Chirag Zhang, Haowen Dilthey, Alexander Aluru, Srinivas Sequence graphs read mapping index sparse matrix-matrix multiplication Graph based non-linear reference structures such as variation graphs and colored de Bruijn graphs enable incorporation of full genomic diversity within a population. However, transitioning from a simple string-based reference to graphs requires addressing many computational challenges, one of which concerns accurately mapping sequencing read sets to graphs. Paired-end Illumina sequencing is a commonly used sequencing platform in genomics, where the paired-end distance constraints allow disambiguation of repeats. Many recent works have explored provably good index-based and alignment-based strategies for mapping individual reads to graphs. However, validating distance constraints efficiently over graphs is not trivial, and existing sequence to graph mappers rely on heuristics. We introduce a mathematical formulation of the problem, and provide a new algorithm to solve it exactly. We take advantage of the high sparsity of reference graphs, and use sparse matrix-matrix multiplications (SpGEMM) to build an index which can be queried efficiently by a mapping algorithm for validating the distance constraints. Effectiveness of the algorithm is demonstrated using real reference graphs, including a human MHC variation graph, and a pan-genome de-Bruijn graph built using genomes of 20 B. anthracis strains. While the one-time indexing time can vary from a few minutes to a few hours using our algorithm, answering a million distance queries takes less than a second. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chirag Jain and Haowen Zhang and Alexander Dilthey and Srinivas Aluru 2019 Is Part Of LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2019.17 urn:nbn:de:0030-drops-110470 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.17 eng https://creativecommons.org/licenses/by/3.0/legalcode