Title |
A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
|
---|---|
Published in |
Algorithms for Molecular Biology, June 2015
|
DOI | 10.1186/s13015-015-0046-4 |
Pubmed ID | |
Authors |
Gustavo Sacomoto, Vincent Lacroix, Marie-France Sagot |
Abstract |
The problem of enumerating bubbles with length constraints in directed graphs arises in transcriptomics where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq. We present a new algorithm for enumerating bubbles with length constraints in weighted directed graphs. This is the first polynomial delay algorithm for this problem and we show that in practice, it is faster than previous approaches. This settles one of the main open questions from Sacomoto et al. (BMC Bioinform 13:5, 2012). Moreover, the new algorithm allows us to deal with larger instances and possibly detect longer alternative splicing events. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
France | 1 | 20% |
United Kingdom | 1 | 20% |
United States | 1 | 20% |
Unknown | 2 | 40% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Scientists | 4 | 80% |
Members of the public | 1 | 20% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 3 | 100% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Researcher | 1 | 33% |
Student > Master | 1 | 33% |
Unknown | 1 | 33% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 2 | 67% |
Unknown | 1 | 33% |