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

BACKGROUND: 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. RESULTS: We present a new algorithm for enumerating bubbles with le...

Descripción completa

Detalles Bibliográficos
Autores principales: Sacomoto, Gustavo, Lacroix, Vincent, Sagot, Marie-France
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2015
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4483228/
https://www.ncbi.nlm.nih.gov/pubmed/26120359
http://dx.doi.org/10.1186/s13015-015-0046-4
_version_ 1782378522981957632
author Sacomoto, Gustavo
Lacroix, Vincent
Sagot, Marie-France
author_facet Sacomoto, Gustavo
Lacroix, Vincent
Sagot, Marie-France
author_sort Sacomoto, Gustavo
collection PubMed
description BACKGROUND: 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. RESULTS: 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. CONCLUSION: 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.
format Online
Article
Text
id pubmed-4483228
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-44832282015-06-28 A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs Sacomoto, Gustavo Lacroix, Vincent Sagot, Marie-France Algorithms Mol Biol Research BACKGROUND: 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. RESULTS: 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. CONCLUSION: 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. BioMed Central 2015-06-27 /pmc/articles/PMC4483228/ /pubmed/26120359 http://dx.doi.org/10.1186/s13015-015-0046-4 Text en © Sacomoto et al. 2015 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Research
Sacomoto, Gustavo
Lacroix, Vincent
Sagot, Marie-France
A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title_full A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title_fullStr A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title_full_unstemmed A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title_short A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
title_sort polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4483228/
https://www.ncbi.nlm.nih.gov/pubmed/26120359
http://dx.doi.org/10.1186/s13015-015-0046-4
work_keys_str_mv AT sacomotogustavo apolynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs
AT lacroixvincent apolynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs
AT sagotmariefrance apolynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs
AT sacomotogustavo polynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs
AT lacroixvincent polynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs
AT sagotmariefrance polynomialdelayalgorithmfortheenumerationofbubbleswithlengthconstraintsindirectedgraphs

Ejemplares similares