Computational Biology
@ Comenius University in Bratislava

Brona Brejova, Travis Gagie, Eva Herencsarova, Tomas Vinar. Maximum-scoring path sets on pangenome graphs of constant treewidth. Frontiers in Bioinformatics, 4:1391086. 2024.

Download preprint: not available

Download from publisher: https://doi.org/10.3389/fbinf.2024.1391086

Related web page: not available

Bibliography entry: BibTeX

Abstract:

We generalize a problem of finding maximum-scoring segment sets, previously 
studied by Csuros (IEEE/ACM Transactions on Computational Biology and 
Bioinformatics, 2004, 1, 139-150), from sequences to graphs. Namely, given a 
vertex-weighted graph G and a non-negative startup penalty c, we can find a set 
of vertex-disjoint paths in G with maximum total score when each path's score is 
its vertices' total weight minus c. We call this new problem maximum-scoring path 
sets (MSPS). We present an algorithm that has a linear-time complexity for graphs 
with a constant treewidth. Generalization from sequences to graphs allows the 
algorithm to be used on pangenome graphs representing several related genomes and 
can be seen as a common abstraction for several biological problems on 
pangenomes, including searching for CpG islands, ChIP-seq data analysis, analysis 
of region enrichment for functional elements, or simple chaining problems.