Eva Herencsárová, Broňa Brejová. Identifying Clusters in Graph Representations of Genomes. In Proceedings of the 23rd Conference Information Technologies – Applications and Theory (ITAT 2023), 3498 volume of CEUR Workshop Proceedings, pp. 232-241, Tatranske Matliare, 2023.
Download preprint: not available
Download from publisher: https://ceur-ws.org/Vol-3498/paper30.pdf
Related web page: not available
Bibliography entry: BibTeX
See also: early version
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.