Computational Biology
@ Comenius University in Bratislava

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

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.