Academic Journal
A family of tree-based generators for bubbles in directed graphs
| العنوان: | A family of tree-based generators for bubbles in directed graphs |
|---|---|
| المؤلفون: | Acuña, Vicente, Soares de Lima, Leandro, Ishi, Italiano, Giuseppe, F, Sciarria, Luca, Pepè, Sagot, Marie-France, Sinaimeri, Blerina |
| المساهمون: | Center for Mathematical Modeling (CMM), Universidad de Chile = University of Chile Santiago (UCHILE), European Bioinformatics Institute Hinxton (EMBL-EBI), EMBL Heidelberg, Libera Università Internazionale degli Studi Sociali Guido Carli Roma (LUISS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Università degli Studi di Roma Tor Vergata Roma, Italia = University of Rome Tor Vergata Rome, Italy = Université de Rome Tor Vergata Rome, Italie, Département PEGASE LBBE (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE23-0001,ASTER,Algorithmes et outils logiciels pour le séquençage d'ARN de troisième génération(2016) |
| المصدر: | ISSN: 1526-1719 ; Journal of Graph Algorithms and Applications ; https://inria.hal.science/hal-03504540 ; Journal of Graph Algorithms and Applications, 2021, 25 (1), pp.549-562. ⟨10.7155/jgaa.00572⟩. |
| بيانات النشر: | HAL CCSD Brown University |
| سنة النشر: | 2021 |
| المجموعة: | Université de Lyon: HAL |
| مصطلحات موضوعية: | bubble generator, directed graphs, alternative splicing, [INFO]Computer Science [cs], [SDV.GEN]Life Sciences [q-bio]/Genetics |
| الوصف: | International audience ; Bubbles are pairs of internally vertex-disjoint (s, t)-paths in a directed graph. In de Bruijn graphs built from reads of RNA and DNA data, bubbles represent interesting biological events, such as alternative splicing (AS) and allelic differences (SNPs and indels). However, the set of all bubbles in a de Bruijn graph built from real data is usually too large to be efficiently enumerated and analysed in practice. In particular, despite significant research done in this area, listing bubbles still remains the main bottleneck for tools that detect AS events in a reference-free context. Recently, in [1] the concept of a bubble generator was introduced as a way for obtaining a compact representation of the bubble space of a graph. Although this bubble generator was quite effective in finding AS events, preliminary experiments showed that it is about 5 times slower than state-of-art methods. In this paper we propose a new family of bubble generators which improve substantially on previous work: bubble generators in this new family are about two orders of magnitude faster and are still able to achieve similar precision in identifying AS events. To highlight the practical value of our new bubble generators, we also report some experimental results on real datasets. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| DOI: | 10.7155/jgaa.00572 |
| الاتاحة: | https://inria.hal.science/hal-03504540 https://inria.hal.science/hal-03504540v1/document https://inria.hal.science/hal-03504540v1/file/luca-jgaa.pdf https://doi.org/10.7155/jgaa.00572 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.8D4AA834 |
| قاعدة البيانات: | BASE |
| DOI: | 10.7155/jgaa.00572 |
|---|