Eva Herencsarova, Brona Brejova. Identifying Clusters in Graph Representations of Genomes. Technical Report 2023.07.20.549917, bioRxiv, 2023.
Download preprint: not available
Download from publisher: https://www.biorxiv.org/content/10.1101/2023.07.20.549917.full.pdf
Related web page: not available
Bibliography entry: BibTeX
In many bioinformatics applications the task is to identify biologically significant locations in an individual genome. In our work, we are interested in finding high-density clusters of such biologically meaningful locations in a graph representation of a pangenome, which is a collection of related genomes. Different formulations of finding such clusters were previously studied for sequences. In this work, we study an extension of this problem for graphs, which we formalize as finding a set of vertex- disjoint paths with a maximum score in a weighted directed graph. We provide a linear-time algorithm for a special class of graphs corresponding to elastic-degenerate strings, one of pangenome representations. We also provide a fixed-parameter tractable algorithm for directed acyclic graphs with a special path decomposition of a limited width.