Computational Biology
@ Comenius University in Bratislava

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

Abstract:

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.