Search

Your search keyword '"Gustavo Sacomoto"' showing total 30 results
Start Over Author "Gustavo Sacomoto"
30 results on '"Gustavo Sacomoto"'

18. On Bubble Generators in Directed Graphs

Author

Roberto Grossi, Romeo Rizzi, Gustavo Sacomoto, Vicente Acuña, Giuseppe F. Italiano, Marie-France Sagot, Blerina Sinaimeri, Leandro Lima, Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), University of Pisa - Università di Pisa, 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), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), University of Verona (UNIVR), ANR-16-CE23-0001,ASTER,Algorithmes et outils logiciels pour le séquençage d'ARN de troisième génération(2016), Università degli studi di Verona = University of Verona (UNIVR), Center for Mathematical Modeling (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE), and Università degli Studi di Roma Tor Vergata [Roma]

Subjects
0301 basic medicine, Bubbles, Bubble generator set, Decomposition algorithm, General Computer Science, Computer science, Bubble, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, De Bruijn graph, Theoretical Computer Science, Physics::Fluid Dynamics, 03 medical and health sciences, symbols.namesake, Decomposition algorithm, 0202 electrical engineering, electronic engineering, information engineering, Data_FILES, Symmetric difference, ComputingMilieux_MISCELLANEOUS, Quantitative Biology::Biomolecules, Mathematics::Combinatorics, Hardware_MEMORYSTRUCTURES, Applied Mathematics, Computer Science (all), Directed graph, Quantitative Biology::Genomics, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Graph, Computer Science Applications, 030104 developmental biology, Compact space, 010201 computation theory & mathematics, Theory of computation, Exponential number, symbols, Bubble space, Bubble generator set, Bubbles, 020201 artificial intelligence & image processing, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni, Algorithm
Abstract

International audience; Bubbles are pairs of internally vertex-disjoint (s, t)-paths with applications in the processing of DNA and RNA data. For example, enumerating alternative splicing events in a reference-free context can be done by enumerating all bubbles in a de Bruijn graph built from RNA-seq reads [16]. However, listing and analysing all bubbles in a given graph is usually unfeasible in practice, due to the exponential number of bubbles present in real data graphs. In this paper, we propose a notion of a bubble generator set, i.e. a polynomial-sized subset of bubbles from which all the others can be obtained through the application of a specific symmetric difference operator. This set provides a compact representation of the bubble space of a graph, which can be useful in practice since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. Furthermore, we provide a polynomial-time algorithm to decompose any bubble of a graph into the bubbles of such a generator in a tree-like fashion.

Published
2019
Full Text
View/download PDF

19. Computing and Listing st-Paths in Public Transportation Networks

Author

Gustavo Sacomoto, Luca Häfliger, Marie-France Sagot, Kateřina Böhmová, Matúš Mihalák, Tobias Pröger, RS: FSE DACS NSO, and DKE Scientific staff

Subjects
Sequence, Polynomial, 021103 operations research, Concatenation, 0211 other engineering and technologies, Public transportation, 0102 computer and information sciences, 02 engineering and technology, Directed graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Listing algorithm, NP-hardness, Computational Theory and Mathematics, 010201 computation theory & mathematics, 11. Sustainability, Line (geometry), Path (graph theory), Theory of computation, Order (group theory), K SHORTEST PATHS, Mathematics
Abstract

Given a set of directed paths (called lines) L, a public transportation network is a directed graph G L = (V L , A L ) which contains exactly the vertices and arcs of every line l ∈ L. An st-route is a pair (π, γ) where γ = 〈l 1,…, l h 〉 is a line sequence and π is an st-path in G L which is the concatenation of subpaths of the lines l 1,…, l h , in this order. Given a threshold β, we present an algorithm for listing all st-paths π for which a route (π, γ) with |γ| ≤ β exists, and we show that the running time of this algorithm is polynomial with respect to the input and the output size. We also present an algorithm for listing all line sequences γ with |γ| ≤ β for which a route (π, γ) exists, and show how to speed it up using preprocessing. Moreover, we show that for the problem of finding an st-route (π, γ) that minimizes the number of different lines in γ, even computing an $o(\log |V|)$ -approximation is NP-hard.

Published
2018

20. Annotation and differential analysis of alternative splicing using de novo assembly of RNAseq data

Author

Amandine E. Rey, Clara Benoit-Pilven, Vincent Lacroix, Camille Marchet, Marie-Pierre Lambert, Gustavo Sacomoto, Leandro Lima, Emilie Chautard, Cyril F. Bourgeois, Didier Auboeuf, Laboratoire de biologie et modélisation de la cellule (LBMC UMR 5239), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de la Santé et de la Recherche Médicale (INSERM), 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), École normale supérieure - Lyon (ENS Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), École normale supérieure de Lyon (ENS de Lyon), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)

Subjects
Genetics, 0303 health sciences, Alternative splicing, Sequence assembly, Computational biology, Biology, de novo assembly, ENCODE, Exon skipping, 03 medical and health sciences, Exon, alternative splicing, 0302 clinical medicine, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], RNA splicing, Human genome, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], transcriptome, 030217 neurology & neurosurgery, 030304 developmental biology, Reference genome
Abstract

Genome-wide analyses reveal that more than 90% of multi exonic human genes produce at least two transcripts through alternative splicing (AS). Various bioinformatics methods are available to analyze AS from RNAseq data. Most methods start by mapping the reads to an annotated reference genome, but some start by a de novo assembly of the reads. In this paper, we present a systematic comparison of a mapping-first approach (FaRLine) and an assembly-first approach (KisSplice). These two approaches are event-based, as they focus on the regions of the transcripts that vary in their exon content. We applied these methods to an RNAseq dataset from a neuroblastoma SK-N-SH cell line (ENCODE) differentiated or not using retinoic acid. We found that the predictions of the two pipelines overlapped (70% of exon skipping events were common), but with noticeable differences. The assembly-first approach allowed to find more novel variants, including novel unannotated exons and splice sites. It also predicted AS in families of paralog genes. The mapping-first approach allowed to find more lowly expressed splicing variants, and was better in predicting exons overlapping repeated elements. This work demonstrates that annotating AS with a single approach leads to missing a large number of candidates. We further show that these candidates cannot be neglected, since many of them are differentially regulated across conditions, and can be validated experimentally. We therefore advocate for the combine use of both mapping-first and assembly-first approaches for the annotation and differential analysis of AS from RNAseq data.

Published
2017

21. Playing hide and seek with repeats in local and global de novo transcriptome assembly of short RNA-seq reads

Author

Leandro, Lima, Blerina, Sinaimeri, Gustavo, Sacomoto, Helene, Lopez-Maestre, Camille, Marchet, Vincent, Miele, Marie-France, Sagot, and Vincent, Lacroix

Subjects
Transcriptome assembly, Research, Enumeration algorithm, Assembly evaluation, RNA-seq, Repeats, Formal model for representing repeats, De Bruijn graph topology, Alternative splicing
Abstract

Background The main challenge in de novo genome assembly of DNA-seq data is certainly to deal with repeats that are longer than the reads. In de novo transcriptome assembly of RNA-seq reads, on the other hand, this problem has been underestimated so far. Even though we have fewer and shorter repeated sequences in transcriptomics, they do create ambiguities and confuse assemblers if not addressed properly. Most transcriptome assemblers of short reads are based on de Bruijn graphs (DBG) and have no clear and explicit model for repeats in RNA-seq data, relying instead on heuristics to deal with them. Results The results of this work are threefold. First, we introduce a formal model for representing high copy-number and low-divergence repeats in RNA-seq data and exploit its properties to infer a combinatorial characteristic of repeat-associated subgraphs. We show that the problem of identifying such subgraphs in a DBG is NP-complete. Second, we show that in the specific case of local assembly of alternative splicing (AS) events, we can implicitly avoid such subgraphs, and we present an efficient algorithm to enumerate AS events that are not included in repeats. Using simulated data, we show that this strategy is significantly more sensitive and precise than the previous version of KisSplice (Sacomoto et al. in WABI, pp 99–111, 1), Trinity (Grabherr et al. in Nat Biotechnol 29(7):644–652, 2), and Oases (Schulz et al. in Bioinformatics 28(8):1086–1092, 3), for the specific task of calling AS events. Third, we turn our focus to full-length transcriptome assembly, and we show that exploring the topology of DBGs can improve de novo transcriptome evaluation methods. Based on the observation that repeats create complicated regions in a DBG, and when assemblers try to traverse these regions, they can infer erroneous transcripts, we propose a measure to flag transcripts traversing such troublesome regions, thereby giving a confidence level for each transcript. The originality of our work when compared to other transcriptome evaluation methods is that we use only the topology of the DBG, and not read nor coverage information. We show that our simple method gives better results than Rsem-Eval (Li et al. in Genome Biol 15(12):553, 4) and TransRate (Smith-Unna et al. in Genome Res 26(8):1134–1144, 5) on both real and simulated datasets for detecting chimeras, and therefore is able to capture assembly errors missed by these methods.

Published
2016

22. Colib’read on galaxy: a tools suite dedicated to biological information extraction from raw NGS reads

Author

Eric Rivals, Bastien Cazaux, Gustavo Sacomoto, Leena Salmela, Camille Marchet, Yvan Le Bras, Raluca Uricaru, Olivier Collin, Alexan Andrieux, Cyril Monjeaud, Susete Alves-Carvalho, Amal Zine El Aabidine, Vincent Miele, Claire Lemaitre, Pierre Peterlongo, Vincent Lacroix, Service Expérimentation et Développement (SED [Rennes]), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Plateforme bioinformatique GenOuest [Rennes], Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Plateforme Génomique Santé Biogenouest®-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec, Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), 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), Institut de Biologie Computationnelle (IBC), Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Inria Rennes – Bretagne Atlantique, Helsinki Institute for Information Technology (HIIT), Aalto University, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Centre de Bioinformatique de Bordeaux (CBIB), CGFB, Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Université de Rennes (UR)-Plateforme Génomique Santé Biogenouest®-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Plateforme Génomique Santé Biogenouest®-Inria Rennes – Bretagne Atlantique, Université de Montpellier (UM)-Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Aalto University-University of Helsinki, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Computer Science, Helsinki Institute for Information Technology, Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan), Genome-scale Algorithmics research group / Veli Mäkinen, Bioinformatics, and Algorithmic Bioinformatics

Subjects
0301 basic medicine, Computer science, Molecular Sequence Data, 0206 medical engineering, Information Storage and Retrieval, Health Informatics, 02 engineering and technology, computer.software_genre, Whole-genome assembly-less treatment, De Bruijn graph, Set (abstract data type), 03 medical and health sciences, symbols.namesake, Bloom filter, Software, Variant calling, Technical Note, Cluster Analysis, Genome, Base Sequence, business.industry, Suite, Computational Biology, High-Throughput Nucleotide Sequencing, Reproducibility of Results, Genomics, 113 Computer and information sciences, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Computer Science Applications, Information extraction, 030104 developmental biology, long read correction, NGS, Memory footprint, symbols, Data mining, Metagenomics, RNA-seq, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Raw data, business, computer, 020602 bioinformatics
Abstract

Background With next-generation sequencing (NGS) technologies, the life sciences face a deluge of raw data. Classical analysis processes for such data often begin with an assembly step, needing large amounts of computing resources, and potentially removing or modifying parts of the biological information contained in the data. Our approach proposes to focus directly on biological questions, by considering raw unassembled NGS data, through a suite of six command-line tools. Findings Dedicated to ‘whole-genome assembly-free’ treatments, the Colib’read tools suite uses optimized algorithms for various analyses of NGS datasets, such as variant calling or read set comparisons. Based on the use of a de Bruijn graph and bloom filter, such analyses can be performed in a few hours, using small amounts of memory. Applications using real data demonstrate the good accuracy of these tools compared to classical approaches. To facilitate data analysis and tools dissemination, we developed Galaxy tools and tool shed repositories. Conclusions With the Colib’read Galaxy tools suite, we enable a broad range of life scientists to analyze raw NGS data. More importantly, our approach allows the maximum biological information to be retained in the data, and uses a very low memory footprint. Electronic supplementary material The online version of this article (doi:10.1186/s13742-015-0105-2) contains supplementary material, which is available to authorized users.

Published
2016
Full Text
View/download PDF

23. Navigating in a sea of repeats in RNA-seq without drowning

Author

Vincent Miele, Blerina Sinaimeri, Vincent Lacroix, Gustavo Sacomoto, Camille Marchet, Marie-France Sagot, Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), 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), ABS4NGS ANR project (ANR-11-BINF-0001-06), ANR-12-BS02-0008,Colib'read,Méthodes d'extraction d'information biologique dans les données HTS non assemblées(2012), and European Project: 247073,EC:FP7:ERC,ERC-2009-AdG,SISYPHE(2010)

Subjects
FOS: Computer and information sciences, Theoretical computer science, Exploit, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Directed Graph, Sequence assembly, Quantitative Biology - Quantitative Methods, Synthetic data, De Bruijn graph, Computational Engineering, Finance, and Science (cs.CE), Alternative Splice Event, 03 medical and health sciences, symbols.namesake, 0302 clinical medicine, Transposable Element, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computer Science - Computational Engineering, Finance, and Science, Quantitative Methods (q-bio.QM), 030304 developmental biology, De Bruijn sequence, 0303 health sciences, [SDV.GEN]Life Sciences [q-bio]/Genetics, Recursive Call, Directed graph, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], FOS: Biological sciences, symbols, Alternative Splice, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Alternative Splice, Transposable Element, Directed Graph, Recursive Call, Alternative Splice Event, Heuristics, 030217 neurology & neurosurgery, Flag (geometry)
Abstract

International audience; The main challenge in de novo assembly of NGS data is certainly to deal with repeats that are longer than the reads. This is particularly true for RNA-seq data, since coverage information cannot be used to flag repeated sequences, of which transposable elements are one of the main examples. Most transcriptome assemblers are based on de Bruijn graphs and have no clear and explicit model for repeats in RNA-seq data, relying instead on heuristics to deal with them. The results of this work are twofold. First, we introduce a formal model for representing high copy-number repeats in RNA-seq data and exploit its properties to infer a combinatorial characteristic of repeat-associated subgraphs. We show that the problem of identifying in a de Bruijn graph a subgraph with this characteristic is NP-complete. In a second step, we show that in the specific case of a local assembly of alternative splicing (AS) events, using our combinatorial characterization we can implicitly avoid such subgraphs. In particular, we designed and implemented an algorithm to efficiently identify AS events that are not included in repeated regions. Finally, we validate our results using synthetic data. We also give an indication of the usefulness of our method on real data.

Published
2014
Full Text
View/download PDF

24. Efficiently Listing Bounded Length st-Paths

Author

Marie-France Sagot, Gustavo Sacomoto, Romeo Rizzi, Dipartimento di Matematica e Informatica - Universita Udine (DIMI), Università degli Studi di Udine - University of Udine [Italie], Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), 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-12-BS02-0008,Colib'read,Méthodes d'extraction d'information biologique dans les données HTS non assemblées(2012), and European Project: 247073,EC:FP7:ERC,ERC-2009-AdG,SISYPHE(2010)

Subjects
Discrete mathematics, FOS: Computer and information sciences, shortest paths, Matching (graph theory), Directed graph, Binary logarithm, output sensitive, shortest paths, listing, output sensitive, Combinatorics, Tree traversal, Tree (descriptive set theory), listing, Bounded function, Computer Science - Data Structures and Algorithms, Graph (abstract data type), Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

The problem of listing the $K$ shortest simple (loopless) $st$-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with $n$ vertices and $m$ edges, the most efficient solution is an $O(K(mn + n^2 \log n))$ algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an $O(K(m+n \log n))$ algorithm for the undirected version by Katoh et al. [Networks, 1982], both using $O(Kn + m)$ space. In this work, we consider a different parameterization for this problem: instead of bounding the number of $st$-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only $O(m+n)$ space. Moreover, we provide a unified framework such that the solutions to both parameterizations -- the classic $K$-shortest and the new length-bounded paths -- can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively., 12 pages, accepted to IWOCA 2014

Published
2014

25. Using cascading Bloom filters to improve the memory usage for de Brujin graphs

Author

Gustavo Sacomoto, Kamil Salikhov, Gregory Kucherov, Lomonosov Moscow State University (MSU), Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), 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), Department of Computer Science [Beer-Sheva], Ben-Gurion University of the Negev (BGU), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Kucherov, Gregory, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Department of Mathematical Logic and Theory of Algorithms

Subjects
FOS: Computer and information sciences, J.3, E.2, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Sequencing data, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Bloom filter, Structural Biology, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Representation (mathematics), Molecular Biology, De Bruijn sequence, Genome assembly, Research, Applied Mathematics, [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, Data structure, Hash table, Computational Theory and Mathematics, Next-generation sequencing, de Brujin graph, Algorithm, Large size
Abstract

De Brujin graphs are widely used in bioinformatics for processing next-generation sequencing data. Due to a very large size of NGS datasets, it is essential to represent de Bruijn graphs compactly, and several approaches to this problem have been proposed recently. In this work, we show how to reduce the memory required by the algorithm of [3] that represents de Brujin graphs using Bloom filters. Our method requires 30% to 40% less memory with respect to the method of [3], with insignificant impact to construction time. At the same time, our experiments showed a better query time compared to [3]. This is, to our knowledge, the best practical representation for de Bruijn graphs., Comment: 12 pages, submitted

Published
2014
Full Text
View/download PDF

27. KISSPLICE: de-novo calling alternative splicing events from RNA-seq data

Author

J. Kielbassa, Vincent Lacroix, Pierre Peterlongo, Marie-France Sagot, Pavlos Antoniou, Gustavo Sacomoto, Raluca Uricaru, Rayan Chikhi, Baobab, 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-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), 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), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Amélioration des Plantes et Biotechnologies Végétales (APBV), Institut National de la Recherche Agronomique (INRA)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Arc Alcovna, ANR-10-COSI-0004,MAPPI,Nouvelles approches algorithmiques et bioinformatiques pour l'analyse des grandes masses de données issues des séquenceurs de nouvelle génération.(2010), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, AGROCAMPUS OUEST-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de la Recherche Agronomique (INRA), ANR-2010-COSI-0004,MAPPI,Nouvelles approches algorithmiques et bioinformatiques pour l'analyse des grandes masses de données issues des séquenceurs de nouvelle génération(2010), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche Agronomique (INRA)-Université de Rennes (UR)-AGROCAMPUS OUEST

Subjects
Sequence analysis, 0206 medical engineering, RNA-Seq, 02 engineering and technology, Computational biology, Biology, Biochemistry, Genome, Polymorphism, Single Nucleotide, De Bruijn graph, GRAPHS, Transcriptome, 03 medical and health sciences, symbols.namesake, Structural Biology, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], Humans, natural sciences, Molecular Biology, 030304 developmental biology, Genetics, 0303 health sciences, Models, Statistical, Sequence Analysis, RNA, Applied Mathematics, Alternative splicing, Reference Standards, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], GENOME, Computer Science Applications, Alternative Splicing, Exact algorithm, Proceedings, Tandem Repeat Sequences, symbols, DNA microarray, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], 020602 bioinformatics, Algorithms
Abstract

Background In this paper, we address the problem of identifying and quantifying polymorphisms in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the fundamental idea that each polymorphism corresponds to a recognisable pattern in a De Bruijn graph constructed from the RNA-seq reads, we propose a general model for all polymorphisms in such graphs. We then introduce an exact algorithm, called KIS SPLICE, to extract alternative splicing events. Results We show that KIS SPLICE enables to identify more correct events than general purpose transcriptome assemblers. Additionally, on a 71 M reads dataset from human brain and liver tissues, KIS SPLICE identified 3497 alternative splicing events, out of which 56% are not present in the annotations, which confirms recent estimates showing that the complexity of alternative splicing has been largely underestimated so far. Conclusions We propose new models and algorithms for the detection of polymorphism in RNA-seq data. This opens the way to a new kind of studies on large HTS RNA-seq datasets, where the focus is not the global reconstruction of full-length transcripts, but local assembly of polymorphic regions. KIS SPLICE is available for download at http://alcovna.genouest.org/kissplice/.

Published
2012
Full Text
View/download PDF

28. Efficient bubble enumeration in directed graphs

Author

Nadia Pisanti, Pierluigi Crescenzi, Etienne Birmelé, Rui Ferreira, Marie-France Sagot, Vincent Lacroix, Gustavo Sacomoto, Andrea Marino, Roberto Grossi, Université d'Évry-Val-d'Essonne (UEVE), Université de Florence, Università degli Studi di Firenze = University of Florence (UniFI), Dipartimento di Informatica [Pisa] (DI), University of Pisa - Università di Pisa, An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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-08-BLAN-0293,MIRI,Combinatorial exploration of the molecular landscape and evolution of intimate species relations(2008), European Project: 247073,EC:FP7:ERC,ERC-2009-AdG,SISYPHE(2010), Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Inria Grenoble - Rhône-Alpes, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
0303 health sciences, Theoretical computer science, Computer science, Bubble, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Directed graph, 01 natural sciences, Quantitative Biology::Genomics, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], De Bruijn graph, 03 medical and health sciences, symbols.namesake, 010201 computation theory & mathematics, Enumeration, symbols, De Bruijn graphs, RNA-Seq, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Representation (mathematics), Algorithm, 030304 developmental biology
Abstract

International audience; Polymorphisms in DNA- or RNA-seq data lead to recognisable patterns in a de Bruijn graph representation of the reads obtained by sequencing. such patterns have been called mouths, or bubbles in the literature. They correspond to two vertex-disjoint directed paths between a source $s$ and a target $t$. Due to the high number of such bubbles that may be present in real data, their enumeration is a major issue concerning the efficiency of dedicated algorithms. We propose in this paper the first linear delay algorithm to enumerate all bubbles with a given source.

Published
2012
Full Text
View/download PDF

29. A New Algorithm for Sparse Suffix Trees

Author

Alair Pereira do Lago and Gustavo Sacomoto

Subjects
Compressed suffix array, Theoretical computer science, Computer science, Suffix tree, Generalized suffix tree, Ranging, Data_CODINGANDINFORMATIONTHEORY, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Longest common substring problem, law.invention, 010201 computation theory & mathematics, law, Simple (abstract algebra), Data_FILES, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Suffix, Algorithm, FM-index
Abstract

The sparse suffix trees are suffix trees in which some suffixes are omitted. There are many applications for these structures, ranging from bioinformatics to natural language processing. In many cases, they can replace the complete suffix tree, without decreasing the performance, but with expressive gains in memory consumption. Here, we present a new optimal algorithm to build the sparse suffix tree. That algorithm is simple enough to be implemented and to obtain good results in practice.

Published
2011
Full Text
View/download PDF

30. Lossless filter for multiple repeats with bounded edit distance

Author

Alair Pereira do Lago, Nadia Pisanti, Gustavo Sacomoto, Pierre Peterlongo, Marie-France Sagot, Biological systems and models, bioinformatics and sequences (SYMBIOSE), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Curso Experimental de Ciências Moleculares, Universidade de São Paulo (USP), Instituto de Matemática e Estatística (IME), Dipartimento di Informatica [Pisa] (DI), University of Pisa - Università di Pisa, King‘s College London, An algorithmic view on genomes, cells, and environments (BAMBOO), 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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, and Universidade de São Paulo = University of São Paulo (USP)

Subjects
Similarity (geometry), lcsh:QH426-470, Computer science, 0206 medical engineering, 02 engineering and technology, 03 medical and health sciences, Structural Biology, Fraction (mathematics), lcsh:QH301-705.5, Molecular Biology, 030304 developmental biology, Lossless compression, 0303 health sciences, Sequence, Multiple sequence alignment, Research, Applied Mathematics, [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, lcsh:Genetics, ALGORITMOS GENÉTICOS, lcsh:Biology (General), Computational Theory and Mathematics, Filter (video), Bounded function, Edit distance, Algorithm, 020602 bioinformatics
Abstract

Background Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and of their phylogenetic relationship. Finding such fragments while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice. Results The filter TUIUIU that we introduce in this paper provides a possible solution to this problem. It can be used as a preprocessing step to any multiple alignment or repeats inference method, eliminating a possibly large fraction of the input that is guaranteed not to contain any approximate repeat. It consists in the verification of several strong necessary conditions that can be checked in a fast way. We implemented three versions of the filter. The first is simply a straightforward extension to the case of multiple sequences of an application of conditions already existing in the literature. The second uses a stronger condition which, as our results show, enable to filter sensibly more with negligible (if any) additional time. The third version uses an additional condition and pushes the sensibility of the filter even further with a non negligible additional time in many circumstances; our experiments show that it is particularly useful with large error rates. The latter version was applied as a preprocessing of a multiple alignment tool, obtaining an overall time (filter plus alignment) on average 63 and at best 530 times smaller than before (direct alignment), with in most cases a better quality alignment. Conclusion To the best of our knowledge, TUIUIU is the first filter designed for multiple repeats and for dealing with error rates greater than 10% of the repeats length.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results