Link to bioRxiv paper:
http://biorxiv.org/cgi/content/short/2023.07.20.549917v1?rss=1
Authors: Herencsarova, E., Brejova, B.
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.
Copy rights belong to original authors. Visit the link for more info
Podcast created by Paper Player, LLC
