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
URL : https://doi.org/10.1016/0166-218x(95)00026-n
Digraphs: Theory, Algorithms and Applications, 2008. ,
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.1093/oxfordjournals.molbev.a004169
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
URL : https://doi.org/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
URL : http://pubsonline.informs.org/doi/pdf/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 : https://genomebiology.biomedcentral.com/track/pdf/10.1186/gb-2008-9-9-234?site=genomebiology.biomedcentral.com
Succinct data structures for assembling large genomes, Bioinformatics, vol.18, issue.Suppl. 1, pp.479-486, 2011. ,
DOI : 10.1101/gr.074492.107
URL : https://academic.oup.com/bioinformatics/article-pdf/27/4/479/16903192/btq697.pdf
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/nature10006
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
URL : http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-99.pdf
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time, Lecture Notes in Computer Science, vol.23, issue.3, pp.403-414, 2010. ,
DOI : 10.1007/s00373-007-0738-8
Listing All Maximal Cliques in Large Sparse Real-World Graphs, Lecture Notes in Computer Science, vol.33, issue.3, pp.364-375, 2011. ,
DOI : 10.1086/jar.33.4.3629752
URL : http://arxiv.org/abs/1103.0318
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.1137/S0097539794270881
Sense from sequence reads: methods for alignment and assembly, Nature Methods, vol.17, issue.11, 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
URL : https://doi.org/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.156, issue.01, pp.173-214, 2004. ,
DOI : 10.1016/S0169-5347(00)02026-7
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
URL : http://www.cs.ucsb.edu/~suri/psdir/vickrey.ps
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
URL : https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/1471-2105-10-S1-S16?site=bmcbioinformatics.biomedcentral.com
CAP3: A DNA Sequence Assembly Program, Genome Research, vol.9, issue.9, pp.868-877, 1999. ,
DOI : 10.1101/gr.9.9.868
URL : http://genome.cshlp.org/content/9/9/868.full.pdf
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
URL : http://genome.cshlp.org/content/13/1/91.full.pdf
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.6028/jres.078B.020
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. ,
DOI : 10.1007/11841036_42
URL : http://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
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.13, issue.1, pp.755-761, 2009. ,
DOI : 10.1101/gr.809403
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.1089/cmb.1995.2.275
Lecture notes on enumeration algorithms, 2014. ,
Next-generation transcriptome assembly, Nature Reviews Genetics, vol.323, issue.10, pp.1-12, 2011. ,
DOI : 10.1126/science.1162986
URL : https://digital.library.unt.edu/ark:/67531/metadc830328/m2/1/high_res_d/1076789.pdf
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
URL : http://genome.cshlp.org/content/23/3/519.full.pdf
Aggressive assembly of pyrosequencing reads with mates, Bioinformatics, vol.18, issue.24, pp.242818-2824, 2008. ,
DOI : 10.1101/gr.074492.107
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.1128/MCB.14.3.1647
The fragment assembly string graph, Bioinformatics, vol.21, issue.Suppl 2, pp.79-85, 2005. ,
DOI : 10.1093/bioinformatics/bti1114
URL : https://academic.oup.com/bioinformatics/article-pdf/21/suppl_2/ii79/6686032/bti1114.pdf
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.265, issue.12, pp.1344-1349, 2008. ,
DOI : 10.1146/annurev.micro.59.031805.133833
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.1111/j.1365-294X.2010.04948.x
Exploring variation-aware contig graphs for (comparative) metagenomics using MaryGold, Bioinformatics, vol.18, issue.5, 2013. ,
DOI : 10.1101/gr.074492.107
URL : https://academic.oup.com/bioinformatics/article-pdf/29/22/2826/896845/btt502.pdf
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.1090/S0002-9947-1943-0012401-3
URL : http://www.pnas.org/content/109/33/13272.full.pdf
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
URL : http://www.cs.hku.hk/~chin/paper/IDBA-Recomb2010.pdf
Meta-IDBA: a de Novo assembler for metagenomic data, Bioinformatics, vol.4, issue.12, pp.27-94, 2011. ,
DOI : 10.1371/journal.pone.0008407
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. ,
DOI : 10.1145/974614.974643
An Eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences, vol.291, issue.5507, pp.989748-53, 2001. ,
DOI : 10.1126/science.1058040
URL : http://www.pnas.org/content/98/17/9748.full.pdf
Understanding mechanisms underlying human gene expression variation with RNA sequencing, Nature, vol.25, issue.7289, pp.464768-772, 2010. ,
DOI : 10.1038/nature08872
URL : https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3089435/pdf
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.4, issue.6, pp.354-366, 2009. ,
DOI : 10.1038/nmeth1043
URL : https://academic.oup.com/bib/article-pdf/10/4/354/847444/bbp026.pdf
An Optimal Bloom Filter Replacement Based on Matrix Solving, Proceedings, pp.263-273, 2009. ,
DOI : 10.1109/TIT.1986.1057137
URL : http://arxiv.org/pdf/0804.1845v1.pdf
NCBI Reference Sequences: current status, policy and new initiatives, Nucleic Acids Research, vol.25, issue.5, pp.32-36, 2009. ,
DOI : 10.1093/nar/25.5.955
URL : https://academic.oup.com/nar/article-pdf/37/suppl_1/D32/3258106/gkn721.pdf
Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees, Networks, vol.13, issue.2, pp.237-252, 1975. ,
DOI : 10.1109/TCT.1967.1082662
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.12, issue.6, 2013. ,
DOI : 10.1186/1471-2105-12-333
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-00824697
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
URL : http://www.pnas.org/content/74/12/5463.full.pdf
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.4, issue.Suppl. 2, pp.281086-1092, 2012. ,
DOI : 10.1371/journal.pone.0008407
Algorithms in c, part 5: graph algorithms, third edition, 2001. ,
Next-generation DNA sequencing, Nature Biotechnology, vol.105, issue.10, 2008. ,
DOI : 10.1101/gr.8.3.175
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.26, issue.22, pp.321956-960, 2008. ,
DOI : 10.1128/MCB.01248-06
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://www.csee.wvu.edu/~xinl/library/papers/comp/Tarjan_siam1972.pdf
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.1093/bioinformatics/btp352
URL : https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3146043/pdf
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.1093/bioinformatics/btp352
URL : https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3146043/pdf
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.1007/3-540-48686-0_35
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.33, issue.19, pp.500-501, 2007. ,
DOI : 10.1093/nar/gni170
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.1101/SQB.1984.049.01.039
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
URL : https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/1471-2105-13-S6-S1?site=bmcbioinformatics.biomedcentral.com
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
URL : http://genome.cshlp.org/content/18/5/821.full.pdf
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 ,