Faster algorithms for the shortest path problem, Journal of the ACM, vol.37, issue.2, pp.213-223, 1990. ,
DOI : 10.1145/77600.77615
Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1999. ,
DOI : 10.1007/978-3-642-58412-1
Reverse search for enumeration, Discrete Applied Mathematics, vol.65, issue.1-3, pp.21-46, 1993. ,
DOI : 10.1016/0166-218X(95)00026-N
Digraphs: Theory, Algorithms and Applications, 2008. ,
DOI : 10.1007/978-1-84800-998-1
SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing, Journal of Computational Biology, vol.19, issue.5, pp.455-477, 2012. ,
DOI : 10.1089/cmb.2012.0021
A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs, pp.742-755, 2010. ,
DOI : 10.1137/1.9781611973075.61
Enumeration in graphs, 1987. ,
Efficient Bubble Enumeration in Directed Graphs, SPIRE, pp.118-129, 2012. ,
DOI : 10.1007/978-3-642-34109-0_13
Optimal Listing of Cycles and st-Paths in Undirected Graphs, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.1884-1896, 2013. ,
DOI : 10.1137/1.9781611973105.134
Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project, Nature, vol.12, issue.7146, pp.447799-816, 2007. ,
DOI : 10.1038/nature05874
The Complete Genome Sequence of Escherichia coli K-12, Science, vol.277, issue.5331, pp.2771453-1462, 1997. ,
DOI : 10.1126/science.277.5331.1453
Alternative Splicing: New Insights from Global Analyses, Cell, vol.126, issue.1, pp.37-47, 2006. ,
DOI : 10.1016/j.cell.2006.06.023
Succinct de Bruijn Graphs, Algorithms in Bioinformatics -12th International Workshop, WABI 2012 Proceedings, volume 7534 of Lecture Notes in Computer Science, pp.225-235, 2012. ,
DOI : 10.1007/978-3-642-33122-0_18
Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, vol.16, issue.9, pp.575-577, 1973. ,
DOI : 10.1145/362342.362367
Analysis of canonical and non-canonical splice sites in mammalian genomes, Nucleic Acids Research, vol.28, issue.21, pp.4364-4375, 2000. ,
DOI : 10.1093/nar/28.21.4364
The vertex set of a 01-polytope is strongly P-enumerable, Computational Geometry, vol.11, issue.2, pp.103-109, 1998. ,
DOI : 10.1016/S0925-7721(98)00021-2
ALLPATHS: De novo assembly of whole-genome shotgun microreads, Genome Research, vol.18, issue.5, 2008. ,
DOI : 10.1101/gr.7337908
Technical Note???Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming, Operations Research, vol.32, issue.6, pp.1381-1384, 1984. ,
DOI : 10.1287/opre.32.6.1381
Short read fragment assembly of bacterial genomes, Genome Research, vol.18, issue.2, pp.324-330, 2008. ,
DOI : 10.1101/gr.7088808
Priority Queues and Dijkstra's Algorithm, 2007. ,
Space-efficient and exact de Bruijn graph representation based on a Bloom filter, Algorithms in Bioinformatics -12th International Workshop, WABI 2012 Proceedings, volume 7534 of Lecture Notes in Computer Science, pp.236-248, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00753930
Stem cell transcriptome profiling via massive-scale mRNA sequencing, Nature Methods, vol.3, issue.7, pp.613-619, 2008. ,
DOI : 10.1038/nmeth.1223
Transcriptome content and dynamics at singlenucleotide resolution, Genome Biology, vol.9, issue.9, pp.1-4, 2008. ,
DOI : 10.1186/gb-2008-9-9-234
URL : http://doi.org/10.1186/gb-2008-9-9-234
Succinct data structures for assembling large genomes, Bioinformatics, vol.27, issue.4, pp.479-486, 2011. ,
DOI : 10.1093/bioinformatics/btq697
URL : http://arxiv.org/abs/1008.2555
Introduction to Algorithms, 2001. ,
Generalized best-first search strategies and the optimality af A*, Journal of the ACM, vol.32, issue.3, pp.505-536, 1985. ,
DOI : 10.1145/3828.3830
Graph Theory (Graduate Texts in Mathematics), 2005. ,
Landscape of transcription in human cells, Nature, vol.474, issue.7414, pp.489101-108, 2012. ,
DOI : 10.1038/nature11233
URL : https://hal.archives-ouvertes.fr/hal-01216755
SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing, Genome Research, vol.17, issue.11, pp.1697-1706, 2007. ,
DOI : 10.1101/gr.6435207
An Appraisal of Some Shortest-Path Algorithms, Operations Research, vol.17, issue.3, pp.395-412, 1969. ,
DOI : 10.1287/opre.17.3.395
Matching: A Well-Solved Class of Integer Linear Programs, Combinatorial structures and their applications, pp.89-92, 1970. ,
DOI : 10.1007/3-540-36478-1_3
An expert system for transmission line route selection, Int. Power Engineering Conf, pp.697-702, 1993. ,
Finding the k Shortest Paths, SIAM Journal on Computing, vol.28, issue.2, pp.652-673, 1999. ,
DOI : 10.1137/S0097539795290477
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time, Lecture Notes in Computer Science, vol.6506, issue.1, pp.403-414, 2010. ,
DOI : 10.1007/978-3-642-17517-6_36
Listing All Maximal Cliques in Large Sparse Real-World Graphs, Lecture Notes in Computer Science, vol.6630, pp.364-375, 2011. ,
DOI : 10.1007/978-3-642-20662-7_31
Indexing compressed text, Journal of the ACM, vol.52, issue.4, pp.552-581, 2005. ,
DOI : 10.1145/1082036.1082039
Output-Sensitive Listing of Bounded-Size Trees in Undirected Graphs, ESA, pp.275-286, 2011. ,
DOI : 10.1007/978-3-642-23719-5_24
Sense from sequence reads: methods for alignment and assembly, Nature Methods, vol.17, issue.11s, pp.6-12, 2009. ,
DOI : 10.1093/bioinformatics/btp352
The directed subgraph homeomorphism problem, Theoretical Computer Science, vol.10, issue.2, pp.111-121, 1980. ,
DOI : 10.1016/0304-3975(80)90009-2
Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Computational Geometry, vol.8, issue.1, pp.1-12, 1997. ,
DOI : 10.1016/0925-7721(95)00049-6
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
Full-length transcriptome assembly from RNA-Seq data without a reference genome, Nature Biotechnology, vol.30, issue.7, pp.29644-652, 2011. ,
DOI : 10.1101/GR.229202. ARTICLE PUBLISHED ONLINE BEFORE MARCH 2002
Listing bounded length paths, 2014. ,
OPTIMAL, EFFICIENT RECONSTRUCTION OF PHYLOGENETIC NETWORKS WITH CONSTRAINED RECOMBINATION, Journal of Bioinformatics and Computational Biology, vol.02, issue.01, pp.173-214, 2004. ,
DOI : 10.1142/S0219720004000521
Enumerating and counting cycles in bipartite graphs, IEEE Communication Theory Workshop, 2004. ,
De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer, Genome Research, vol.18, issue.5, pp.802-809, 2008. ,
DOI : 10.1101/gr.072033.107
Vickrey prices and shortest paths: what is an edge worth?, Proceedings 2001 IEEE International Conference on Cluster Computing, pp.252-259, 2001. ,
DOI : 10.1109/SFCS.2001.959899
Cyclic pattern kernels for predictive graph mining, Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '04, pp.158-167, 2004. ,
DOI : 10.1145/1014052.1014072
Crystallizing short-read assemblies around seeds, BMC Bioinformatics, vol.10, issue.Suppl 1, 2009. ,
DOI : 10.1186/1471-2105-10-S1-S16
CAP3: A DNA Sequence Assembly Program, Genome Research, vol.9, issue.9, pp.868-877, 1999. ,
DOI : 10.1101/gr.9.9.868
A New Algorithm for DNA Sequence Assembly, Journal of Computational Biology, vol.2, issue.2, pp.291-306, 1995. ,
DOI : 10.1089/cmb.1995.2.291
De novo assembly and genotyping of variants using colored de Bruijn graphs, Nature Genetics, vol.44, issue.2, 2012. ,
DOI : 10.1016/0198-8859(91)90078-N
Whole-Genome Sequence Assembly for Mammalian Genomes: Arachne 2, Genome Research, vol.13, issue.1, pp.91-97, 2003. ,
DOI : 10.1101/gr.828403
Finding All the Elementary Circuits of a Directed Graph, SIAM Journal on Computing, vol.4, issue.1, pp.77-84, 1975. ,
DOI : 10.1137/0204007
On generating all maximal independent sets, Information Processing Letters, vol.27, issue.3, pp.119-123, 1988. ,
DOI : 10.1016/0020-0190(88)90065-8
An efficient algorithm for K shortest simple paths, Networks, vol.17, issue.4, pp.411-427, 1982. ,
DOI : 10.1002/net.3230120406
Exact and approximation algorithms for DNA sequence reconstruction, 1992. ,
BLAT---The BLAST-Like Alignment Tool, Genome Research, vol.12, issue.4, pp.656-664, 2002. ,
DOI : 10.1101/gr.229202
Less hashing, same performance: Building a better bloom filter. Random Structures Algorithms, pp.187-218, 2008. ,
A methodology for the structural and functional analysis of signaling and regulatory networks, BMC Bioinformatics, vol.7, issue.1, p.56, 2006. ,
DOI : 10.1186/1471-2105-7-56
Computing paths and cycles in biological interaction graphs, BMC Bioinformatics, vol.10, issue.1, p.181, 2009. ,
DOI : 10.1186/1471-2105-10-181
The Art of Computer Programming Sorting and Searching, 1998. ,
Enumerating all connected maximal common subgraphs in two graphs, Theoretical Computer Science, vol.250, issue.1-2, pp.1-30, 2001. ,
DOI : 10.1016/S0304-3975(00)00286-3
The UCSC Genome Browser Database: update 2009, Nucleic Acids Research, vol.37, issue.Database, pp.755-761, 2009. ,
DOI : 10.1093/nar/gkn875
Genomic mapping by fingerprinting random clones: A mathematical analysis, Genomics, vol.2, issue.3, pp.231-239, 1988. ,
DOI : 10.1016/0888-7543(88)90007-9
Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem, Management Science, vol.18, issue.7, pp.401-405, 1972. ,
DOI : 10.1287/mnsc.18.7.401
Identifying and Classifying Trait Linked Polymorphisms in Non-Reference Species by Walking Coloured de Bruijn Graphs, PLoS ONE, vol.112, issue.25, p.60058, 2013. ,
DOI : 10.1371/journal.pone.0060058.s010
Comprehensive comparative analysis of strand-specific RNA sequencing methods, Nature Methods, vol.5, issue.9, pp.709-715, 2010. ,
DOI : 10.1038/nmeth.1491
The complexity of finding two disjoint paths with min-max objective function, Discrete Applied Mathematics, vol.26, issue.1, 1990. ,
DOI : 10.1016/0166-218X(90)90024-7
De novo assembly of human genomes with massively parallel short read sequencing, Genome Research, vol.20, issue.2, pp.265-272, 2010. ,
DOI : 10.1101/gr.097261.109
Highly Integrated Single-Base Resolution Maps of the Epigenome in Arabidopsis, Cell, vol.133, issue.3, pp.133523-536, 2008. ,
DOI : 10.1016/j.cell.2008.03.029
A new way to enumerate cycles in graph, AICT and ICIW, pp.57-59, 2006. ,
Genome sequencing in microfabricated high-density picolitre reactors, Nature, vol.2, issue.7057, pp.437376-380, 2005. ,
DOI : 10.1016/0888-7543(88)90007-9
Lecture notes on enumeration algorithms, 2014. ,
Next-generation transcriptome assembly, Nature Reviews Genetics, vol.323, issue.10, pp.1-12, 2011. ,
DOI : 10.1038/nrg3068
On Algorithms for Enumerating All Circuits of a Graph, SIAM Journal on Computing, vol.5, issue.1, pp.90-99, 1976. ,
DOI : 10.1137/0205007
Computability of Models for Sequence Assembly, WABI, Lecture Notes in Computer Science, pp.289-301, 2007. ,
DOI : 10.1007/978-3-540-74126-8_27
iReckon: Simultaneous isoform discovery and abundance estimation from RNA-seq data, Genome Research, vol.23, issue.3, pp.519-529, 2012. ,
DOI : 10.1101/gr.142232.112
Aggressive assembly of pyrosequencing reads with mates, Bioinformatics, vol.24, issue.24, pp.242818-2824, 2008. ,
DOI : 10.1093/bioinformatics/btn548
In situ localized amplification and contact replication of many individual DNA molecules, Nucleic Acids Research, vol.27, issue.24, p.27, 1999. ,
DOI : 10.1093/nar/27.24.e34
Transcriptome genetics using second generation sequencing in a Caucasian population, Nature, vol.4, issue.7289, pp.464773-777, 2010. ,
DOI : 10.1038/nature08903
Mapping and quantifying mammalian transcriptomes by RNA-Seq, Nature Methods, vol.14, issue.7, pp.621-628, 2008. ,
DOI : 10.1038/nmeth.1226
The fragment assembly string graph, Bioinformatics, vol.21, issue.Suppl 2, pp.79-85, 2005. ,
DOI : 10.1093/bioinformatics/bti1114
A Whole-Genome Assembly of Drosophila, Science, vol.287, issue.5461, pp.2872196-204, 2000. ,
DOI : 10.1126/science.287.5461.2196
The Transcriptional Landscape of the Yeast Genome Defined by RNA Sequencing, Science, vol.320, issue.5881, pp.1344-1349, 2008. ,
DOI : 10.1126/science.1158441
MetaVelvet: an extension of Velvet assembler to de novo metagenome assembly from short sequence reads, Proceedings of the 2Nd ACM Conference on Bioinformatics, pp.116-124, 2011. ,
DOI : 10.1093/nar/gks678
Exploring variation-aware contig graphs for (comparative) metagenomics using MaryGold, Bioinformatics, vol.29, issue.22, 2013. ,
DOI : 10.1093/bioinformatics/btt502
Deep surveying of alternative splicing complexity in the human transcriptome by high-throughput sequencing, Nature Genetics, vol.76, issue.12, pp.401413-1415, 2008. ,
DOI : 10.1016/j.molcel.2004.12.004
Scaling metagenome sequence assembly with probabilistic de Bruijn graphs, Proc. Natl, 2012. ,
DOI : 10.1073/pnas.1121464109
IDBA ??? A Practical Iterative de Bruijn Graph De Novo Assembler, Lecture Notes in Computer Science, vol.6044, pp.426-440, 2010. ,
DOI : 10.1007/978-3-642-12683-3_28
Meta-IDBA: a de Novo assembler for metagenomic data, Bioinformatics, vol.27, issue.13, pp.27-94, 2011. ,
DOI : 10.1093/bioinformatics/btr216
Comprehensive analysis of RNA-Seq data reveals extensive RNA editing in a human transcriptome, Nature Biotechnology, vol.460, issue.3, pp.253-260, 2012. ,
DOI : 10.1038/nature06884
Mapsembler, targeted and micro assembly of large NGS datasets on a desktop computer, BMC Bioinformatics, vol.13, issue.1, p.48, 2012. ,
DOI : 10.1186/gb-2011-12-1-r6
URL : https://hal.archives-ouvertes.fr/hal-00784408
Identifying SNPs without a Reference Genome by Comparing Raw Reads, SPIRE, Springer LNCS 6393, pp.147-158, 2010. ,
DOI : 10.1007/978-3-642-16321-0_14
URL : https://hal.archives-ouvertes.fr/inria-00514887
l-tuple DNA sequencing: computer analysis, J. Biomol. Struct. Dyn, issue.7, pp.63-73, 1989. ,
De novo repeat classification and fragment assembly, RECOMB, pp.213-222, 2004. ,
An Eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences, vol.98, issue.17, pp.989748-53, 2001. ,
DOI : 10.1073/pnas.171285098
Understanding mechanisms underlying human gene expression variation with RNA sequencing, Nature, vol.25, issue.7289, pp.464768-772, 2010. ,
DOI : 10.1038/nature08872
Self-Avoiding Paths and the Adjacency Matrix of a Graph, SIAM Journal on Applied Mathematics, vol.14, issue.3, pp.600-609, 1966. ,
DOI : 10.1137/0114051
Genome assembly reborn: recent computational challenges, Briefings in Bioinformatics, vol.10, issue.4, pp.354-366, 2009. ,
DOI : 10.1093/bib/bbp026
An Optimal Bloom Filter Replacement Based on Matrix Solving, Proceedings, pp.263-273, 2009. ,
DOI : 10.1109/TIT.1986.1057137
NCBI Reference Sequences: current status, policy and new initiatives, Nucleic Acids Research, vol.37, issue.Database, pp.32-36, 2009. ,
DOI : 10.1093/nar/gkn721
Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, vol.5, issue.3, pp.237-252, 1975. ,
MetaSim???A Sequencing Simulator for Genomics and Metagenomics, PLoS ONE, vol.13, issue.7, p.3373, 2008. ,
DOI : 10.1371/journal.pone.0003373.s002
DSK: k-mer counting with very low memory usage, Bioinformatics, vol.29, issue.5, 2013. ,
DOI : 10.1093/bioinformatics/btt020
URL : https://hal.archives-ouvertes.fr/hal-00778473
Streaming fragment assignment for real-time analysis of sequencing experiments, Nature Methods, vol.10, issue.1, pp.71-73, 2013. ,
DOI : 10.1093/nar/gkr1246
De novo assembly and analysis of RNA-seq data, Nature Methods, vol.7, issue.11, pp.909-912, 2010. ,
DOI : 10.1038/nbt0509-455
Shortest Simple Paths Problem in Weighted Directed Graphs, SODA, pp.920-928, 2007. ,
DOI : 10.1137/080730950
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs, Lecture Notes in Computer Science, vol.3580, pp.249-260, 2005. ,
DOI : 10.1007/11523468_21
A Polynomial Delay Algorithm for the Enumeration of Bubbles with Length Constraints in Directed Graphs and Its Application to the Detection of Alternative Splicing in RNA-seq Data, WABI, pp.99-111, 2013. ,
DOI : 10.1007/978-3-642-40453-5_9
URL : https://hal.archives-ouvertes.fr/hal-00842982
Kissplice: de-novo calling alternative splicing events from rna-seq data, BMC Bioinformatics, pp.13-19, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00784407
Using cascading bloom filters to improve the memory usage for de brujin graphs, WABI, Lecture Notes in Computer Science, pp.364-376, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00971576
Complete Alternative Splicing Events Are Bubbles in Splicing Graphs, Journal of Computational Biology, vol.16, issue.8, pp.1117-1140, 2009. ,
DOI : 10.1089/cmb.2009.0108
A General Definition and Nomenclature for Alternative Splicing Events, PLoS Computational Biology, vol.3, issue.8, p.1000147, 2008. ,
DOI : 10.1371/journal.pcbi.1000147.s008
URL : https://hal.archives-ouvertes.fr/hal-01412838
DNA sequencing with chain-terminating inhibitors, Proc. Natl. Acad. Sci, p.74, 1977. ,
DOI : 10.1073/pnas.74.12.5463
A time and memory efficient way to enumerate cycles in a graph, 2007 International Conference on Intelligent and Advanced Systems, pp.498-500, 2007. ,
DOI : 10.1109/ICIAS.2007.4658438
Complexity of counting cycles using zeons, Computers & Mathematics with Applications, vol.62, issue.4, pp.1828-1837, 2011. ,
DOI : 10.1016/j.camwa.2011.06.026
URL : https://hal.archives-ouvertes.fr/hal-01280670
Data Structures and Algorithms for Analysis of Alternative Splicing with RNA-Seq Data, 2010. ,
Oases: robust de novo RNA-seq assembly across the dynamic range of expression levels, Bioinformatics, vol.28, issue.8, pp.281086-1092, 2012. ,
DOI : 10.1093/bioinformatics/bts094
Algorithms in c, part 5: graph algorithms, third edition, 2001. ,
Next-generation DNA sequencing, Nature Biotechnology, vol.105, issue.10, 2008. ,
DOI : 10.1038/nbt1486
dbSNP: the NCBI database of genetic variation, Nucleic Acids Research, vol.29, issue.1, pp.308-311, 2001. ,
DOI : 10.1093/nar/29.1.308
ABySS: A parallel assembler for short read sequence data, Genome Research, vol.19, issue.6, p.1117, 2009. ,
DOI : 10.1101/gr.089532.108
Efficient de novo assembly of large genomes using compressed data structures, Genome Research, vol.22, issue.3, pp.549-556, 2012. ,
DOI : 10.1101/gr.126953.111
A strategy of DNA sequencing employing computer programs, Nucleic Acids Research, vol.6, issue.7, pp.2601-2610, 1979. ,
DOI : 10.1093/nar/6.7.2601
A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome, Science, vol.321, issue.5891, pp.321956-960, 2008. ,
DOI : 10.1126/science.1160342
A Graph-Theoretic Algorithm for Matching Chemical Structures., Journal of Chemical Documentation, vol.5, issue.1, pp.36-43, 1965. ,
DOI : 10.1021/c160016a007
An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph, SIAM Journal on Computing, vol.10, issue.4, pp.797-808, 1981. ,
DOI : 10.1137/0210062
A search strategy for the elementary cycles of a directed graph, BIT, vol.19, issue.2, 1976. ,
DOI : 10.1007/BF01931370
Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972. ,
DOI : 10.1137/0201010
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.327.8418
Enumeration of the Elementary Circuits of a Directed Graph, SIAM Journal on Computing, vol.2, issue.3, pp.211-216, 1973. ,
DOI : 10.1137/0202017
Phage assembly suite and tutorial (PHAST), pp.2013-2024, 2013. ,
An efficient search algorithm to find the elementary circuits of a graph, Communications of the ACM, vol.13, issue.12, pp.722-726, 1970. ,
DOI : 10.1145/362814.362819
Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation, Nature Biotechnology, vol.25, issue.5, pp.511-515, 2010. ,
DOI : 10.1038/nbt.1621
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3146043
Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation, Nature Biotechnology, vol.25, issue.5, pp.511-515, 2010. ,
DOI : 10.1038/nbt.1621
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3146043
A Fast Algorithm for Enumerating Bipartite Perfect Matchings, Proc. of the 12th International Symposium on Algorithms and Computation, ISAAC'01, pp.367-379, 2001. ,
DOI : 10.1137/0202019
The complexity of computing the permanent, Theoretical Computer Science, vol.8, issue.2, pp.189-201, 1979. ,
DOI : 10.1016/0304-3975(79)90044-6
Most ???Dark Matter??? Transcripts Are Associated With Known Genes, PLoS Biology, vol.8, issue.5, 2010. ,
DOI : 10.1371/journal.pbio.1000371.s017
Alternative isoform regulation in human tissue transcriptomes, Nature, vol.15, issue.7221, pp.456470-476, 2008. ,
DOI : 10.1038/nature07509
RNA-Seq: a revolutionary tool for transcriptomics, Nature Reviews Genetics, vol.328, issue.1, 2009. ,
DOI : 10.1038/nrg2484
Assembling millions of short DNA sequences using SSAKE, Bioinformatics, vol.23, issue.4, pp.500-501, 2007. ,
DOI : 10.1093/bioinformatics/btl629
Sequence alignments in the neighborhood of the optimum with general application to dynamic programming, Proceedings of the National Academy of Sciences, vol.80, issue.10, pp.3123-3124, 1983. ,
DOI : 10.1073/pnas.80.10.3123
A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs, Journal of the ACM, vol.13, issue.2, pp.205-210, 1966. ,
DOI : 10.1145/321328.321331
A unified classification system for eukaryotic transposable elements, Nature Reviews Genetics, vol.8, issue.12, pp.973-982, 2007. ,
DOI : 10.1038/nrg2165
URL : https://hal.archives-ouvertes.fr/hal-00169819
Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion, Journal of Discrete Algorithms, vol.6, issue.1, pp.93-102, 2008. ,
DOI : 10.1016/j.jda.2007.01.005
Generation of all Hamiltonian Circuits, Paths, and Centers of a Graph, and Related Problems, IEEE Transactions on Circuit Theory, vol.14, issue.1, pp.79-81, 1967. ,
DOI : 10.1109/TCT.1967.1082662
Exploiting sparseness in de novo genome assembly, BMC Bioinformatics, vol.13, issue.Suppl 6, pp.13-14, 2012. ,
DOI : 10.1093/bioinformatics/btr319
Shortest Loopless Paths in a Network, Management Science, vol.17, issue.11, pp.712-716, 1971. ,
DOI : 10.1287/mnsc.17.11.712
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs, Genome Research, vol.18, issue.5, pp.821-829, 2008. ,
DOI : 10.1101/gr.074492.107
Dans cette thèse, nous abordons le problème de l'identification et de la quantification de variants (épissage alternatif et polymorphisme génomique) dans des données de RNA-seq sans génome de référence, et sans faire un assemblage complet des transcripts Basé sur l'idée que chaque variant correspond à une motif reconnaissable, qu'on appelle une bulle, dans un graphe de Bruijn construit à partir des lectures de RNA-seq, nous proposons un modèle pour les variants dans de tels graphes. Nous introduisons ensuite une méthode, appelé KisSplice, pour extraire les événements d'épissage alternatif, et nous montrons qu'il trouve plus d'événements corrects que les assembleurs de transcriptome traditionnels. Afin d'améliorer son temps d'exécution, nous proposons un nouvel algorithme polynomial pour énumérer les bulles. On montre qu'il est plusieurs ordres de grandeur plus rapide que les approches précédentes. Afin de réduire sa consommation en mémoire, nous proposons une nouvelle façon de représenter un graphe de Bruijn. Nous montrons que notre approche utilise 30% à 40% moins de mémoire que l'état de l'art, Nous appliquons les techniques développées pour énumérer les bulles à deux problémes classiques. Nous donnons le premier algorithme optimal pour énumérer les cycles dans des graphes non orientés. Il s nous limitons leurs poids. Nous présentons de nouveaux algorithmes qui utilisent exponentiellement moins mémoire que les approches précédentes ,