A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs

Area of Science:

• Computational Biology
• Bioinformatics
• Graph Theory

Background:

• Identifying alternative splicing events in transcriptomics is crucial for understanding gene expression.
• RNA sequencing (RNA-seq) data analysis involves challenges like enumerating complex biological structures.
• The problem of enumerating bubbles with length constraints in directed graphs is a key computational task in this field.

Purpose of the Study:

• To present a novel algorithm for enumerating bubbles with length constraints in weighted directed graphs.
• To address a significant open question in the analysis of alternative splicing events.

Main Methods:

• Development of a new algorithm for bubble enumeration in weighted directed graphs.
• Implementation of a polynomial delay algorithm for the specified problem.
• Comparative analysis of the new algorithm's performance against existing methods.

Main Results:

• The presented algorithm is the first to offer polynomial delay for enumerating bubbles with length constraints.
• Empirical results demonstrate that the new algorithm is practically faster than prior methods.
• The algorithm successfully handles larger datasets and can detect longer alternative splicing events.

Conclusions:

• This work resolves a major open question in the field of computational transcriptomics.
• The developed algorithm enhances the capability to analyze complex alternative splicing events.
• The findings pave the way for more comprehensive studies of gene expression variations.