{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T01:41:42Z","timestamp":1722994902233},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"S14","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/1471-2105-16-s14-s2","type":"journal-article","created":{"date-parts":[[2015,10,3]],"date-time":"2015-10-03T04:04:47Z","timestamp":1443845087000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Exact approaches for scaffolding"],"prefix":"10.1186","volume":"16","author":[{"given":"Mathias","family":"Weller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,2]]},"reference":[{"issue":"D1","key":"7174_CR1","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1093\/nar\/gku950","volume":"43","author":"TBK Reddy","year":"2014","unstructured":"Reddy TBK, Thomas AD, Stamatis D, Bertsch J, Isbandi M, Jansson J, Mallajosyula J, Pagani I, Lobos EA, Kyrpides NC: The Genomes OnLine Database (GOLD) v.5: a metadata management system based on a four level (meta)genome project classification. Nucleic Acids Research. 2014, 43 (D1): 1099-1106. [\n                    https:\/\/gold.jgi-psf.org\/distribution\n                    \n                  ]","journal-title":"Nucleic Acids Research"},{"issue":"4","key":"7174_CR2","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","volume":"29","author":"N Donmez","year":"2013","unstructured":"Donmez N, Brudno ML: SCARPA: scaffolding reads with practical algorithms. Bioinformatics. 2013, 29 (4): 428-434.","journal-title":"Bioinformatics"},{"issue":"11","key":"7174_CR3","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1093\/bioinformatics\/bts175","volume":"28","author":"AA Gritsenko","year":"2012","unstructured":"Gritsenko AA, Nijkamp JF, Reinders MJT, de Ridder D: GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies. Bioinformatics. 2012, 28 (11): 1429-1437.","journal-title":"Bioinformatics"},{"key":"7174_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1186\/1471-2105-11-345","volume":"11","author":"A Dayarian","year":"2010","unstructured":"Dayarian A, Michael TP, Sengupta AM: SOPRA: Scaffolding algorithm for paired reads via statistical optimization. BMC Bioinformatics. 2010, 11: 345-","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"7174_CR5","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","volume":"18","author":"S Gao","year":"2011","unstructured":"Gao S, Sung W-K, Nagarajan N: Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences. Journal of Computational Biology. 2011, 18 (11): 1681-1691.","journal-title":"Journal of Computational Biology"},{"issue":"23","key":"7174_CR6","doi-asserted-by":"publisher","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","volume":"27","author":"L Salmela","year":"2011","unstructured":"Salmela L, M\u00e4kinen V, V\u00e4lim\u00e4ki N, Ylinen J, Ukkonen E: Fast scaffolding with small independent mixed integer programs. Bioinformatics. 2011, 27 (23): 3259-3265.","journal-title":"Bioinformatics"},{"issue":"4","key":"7174_CR7","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","volume":"27","author":"M Boetzer","year":"2011","unstructured":"Boetzer M, Henkel CV, Jansen HJ, Butler D, Pirovano W: Scaffolding pre-assembled contigs using SSPACE. Bioinformatics. 2011, 27 (4): 578-579.","journal-title":"Bioinformatics"},{"issue":"21","key":"7174_CR8","doi-asserted-by":"publisher","first-page":"2964","DOI":"10.1093\/bioinformatics\/btr520","volume":"27","author":"S Koren","year":"2011","unstructured":"Koren S, Treangen TJ, Pop M: Bambus 2: Scaffolding metagenomes. Bioinformatics. 2011, 27 (21): 2964-2971.","journal-title":"Bioinformatics"},{"key":"7174_CR9","doi-asserted-by":"crossref","unstructured":"Hunt M, Newbold C, Berriman M, Otto T: A comprehensive evaluation of assembly scaffolding tools. Genome Biology. 2014, 15 (3):","DOI":"10.1186\/gb-2014-15-3-r42"},{"issue":"5","key":"7174_CR10","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1145\/585265.585267","volume":"49","author":"DH Huson","year":"2002","unstructured":"Huson DH, Reinert K, Myers EW: The greedy path-merging algorithm for contig scaffolding. Journal of the ACM. 2002, 49 (5): 603-615.","journal-title":"Journal of the ACM"},{"issue":"1","key":"7174_CR11","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1186\/1471-2164-11-616","volume":"11","author":"R Solinhac","year":"2010","unstructured":"Solinhac R, Leroux S, Galkina S, Chazara O, Feve K, Vignoles F, Morisson M, Derjusheva S, Bed'hom B, Vignal A, Fillon V, Pitel F: Integrative mapping analysis of chicken microchromosome 16 organization. BMC Genomics. 2010, 11 (1): 616-","journal-title":"BMC Genomics"},{"key":"7174_CR12","doi-asserted-by":"crossref","unstructured":"Sharpton TJ: An introduction to the analysis of shotgun metagenomic data. Frontiers in Plant Science. 2014, 5 (209):","DOI":"10.3389\/fpls.2014.00209"},{"key":"7174_CR13","volume-title":"The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization","author":"DB Shmoys","year":"1985","unstructured":"Shmoys DB, Lenstra JK, Kan AHGR, Lawler EL: The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization. Edited by: John Wiley & Sons. 1985"},{"key":"7174_CR14","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte WT: A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics. 1954, 6: 347-352.","journal-title":"Canadian Journal of Mathematics"},{"key":"7174_CR15","first-page":"47","volume-title":"AlCoB Lecture Notes in Computer Science","author":"A Chateau","year":"2014","unstructured":"Chateau A, Giroudeau R: Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem. AlCoB Lecture Notes in Computer Science. Edited by: Dediu, A.H., Mart\u00edn-Vide, C., Truthe, B. 2014, Springer, 8542: 47-58."},{"key":"7174_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2015.06.023","volume":"595","author":"A Chateau","year":"2015","unstructured":"Chateau A, Giroudeau R: A complexity and approximation framework for the maximization scaffolding problem. Theoretical Computer Science. 2015, 595: 92-106. doi:10.1016\/j.tcs.2015.06.023","journal-title":"Theoretical Computer Science"},{"key":"7174_CR17","volume-title":"On the implementation of polynomial-time approximation algorithms for scaffold problems","author":"M Weller","year":"2015","unstructured":"Weller M, Chateau A, Giroudeau R: On the implementation of polynomial-time approximation algorithms for scaffold problems. submitted 2015"},{"issue":"3","key":"7174_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1093\/nar\/gkr1000","volume":"40","author":"FV Nieuwerburgh","year":"2012","unstructured":"Nieuwerburgh FV, Thompson RC, Ledesma J, Deforce D, Gaasterland T, Ordoukhanian P, Head SR: Illumina mate-paired DNA sequencing-library preparation using Cre-Lox recombination. Nucleic Acids Research. 2012, 40 (3): 24-24.","journal-title":"Nucleic Acids Research"},{"issue":"4","key":"7174_CR19","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","volume":"27","author":"M Boetzer","year":"2011","unstructured":"Boetzer M, Henkel CV, Jansen HJ, Butler D, Pirovano W: Scaffolding pre-assembled contigs using SSPACE. Bioinformatics. 2011, 27 (4): 578-579.","journal-title":"Bioinformatics"},{"issue":"4","key":"7174_CR20","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed B, Smith K, Vetta A: Finding odd cycle transversals. Operations Research Letters. 2004, 32 (4): 299-301.","journal-title":"Operations Research Letters"},{"issue":"1","key":"7174_CR21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1186\/1471-2105-15-281","volume":"15","author":"K Sahlin","year":"2014","unstructured":"Sahlin K, Vezzi F, Nystedt B, Lundeberg J, Arvestad L: BESST - efficient scaffolding of large fragmented assemblies. BMC Bioinformatics. 2014, 15 (1): 281-","journal-title":"BMC Bioinformatics"},{"key":"7174_CR22","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-319-12418-6_17","volume":"8826","author":"N Luhmann","year":"2014","unstructured":"Luhmann N, Chauve C, Stoye J, Wittler R: Scaffolding of ancient contigs and ancestral reconstruction in a phylogenetic framework. Proceedings of Brazilian Symposium on Bioinformatics Lecture Notes in Computer Science. 2014, 8826: 135-143.","journal-title":"Proceedings of Brazilian Symposium on Bioinformatics Lecture Notes in Computer Science"},{"issue":"23","key":"7174_CR23","doi-asserted-by":"publisher","first-page":"2987","DOI":"10.1093\/bioinformatics\/btt527","volume":"29","author":"A Rajaraman","year":"2013","unstructured":"Rajaraman A, Tannier E, Chauve C: FPSAC: Fast Phylogenetic Scaffolding of Ancient Contigs. Bioinformatics. 2013, 29 (23): 2987-2994.","journal-title":"Bioinformatics"},{"key":"7174_CR24","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.compbiolchem.2015.02.005","volume":"57","author":"S Aganezov","year":"2015","unstructured":"Aganezov S, Sitdykovaa N, Alekseyev MA: AGCConsortium: Scaffold assembly based on genome rearrangement analysis. Computational Biology and Chemistry. 2015, 57: 46-53.","journal-title":"Computational Biology and Chemistry"},{"issue":"4","key":"7174_CR25","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F: Which Problems Have Strongly Exponential Complexity?. Journal of Computer and System Sciences. 2001, 63 (4): 512-530.","journal-title":"Journal of Computer and System Sciences"},{"key":"7174_CR26","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender HL, Cygan M, Kratsch S, Nederlof J, Impagliazzo R, Paturi R, Zane F: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation. 2015, 243: 86-111.","journal-title":"Information and Computation"},{"key":"7174_CR27","volume-title":"Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey RG, Fellows MR: Fundamentals of Parameterized Complexity. Texts in Computer Science. 2013, Springer"},{"issue":"16","key":"7174_CR28","doi-asserted-by":"publisher","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N, Marth G, Abecasis G, Durbin R: The sequence alignment\/map format and SAMtools. Bioinformatics. 2009, 25 (16): 2078-2079.","journal-title":"Bioinformatics"},{"key":"7174_CR29","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1748-7188-8-22","volume":"8","author":"R Chikhi","year":"2013","unstructured":"Chikhi R, Rizk G: Space-efficient and exact de bruijn graph representation based on a bloom filter. Algorithms for Molecular Biology. 2013, 8: 22-","journal-title":"Algorithms for Molecular Biology"},{"issue":"5","key":"7174_CR30","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li H, Durbin R: Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics. 2010, 26 (5): 589-595.","journal-title":"Bioinformatics"},{"key":"7174_CR31","volume-title":"Workshop Constraints in Bioinformatics","author":"N Briot","year":"2014","unstructured":"Briot N, Chateau A, Coletta R, Givry SD, Leleux P, Schiex T: An Integer Linear Programming Approach for Genome Scaffolding. Workshop Constraints in Bioinformatics. 2014"},{"issue":"3","key":"7174_CR32","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1101\/gr.131383.111","volume":"22","author":"SL Salzberg","year":"2012","unstructured":"Salzberg SL, Phillippy AM, Zimin A, Puiu D, Magoc T, Koren S, Treangen TJ, Schatz MC, Delcher AL, Roberts M, Marc\u00b8ais G, Pop M, Yorke JA: GAGE: A critical evaluation of genome assemblies and assembly algorithms. Genome Research. 2012, 22 (3): 557-567. [\n                    http:\/\/gage.cbcb.umd.edu\n                    \n                  ]","journal-title":"Genome Research"},{"issue":"5","key":"7174_CR33","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"DR Zerbino","year":"2008","unstructured":"Zerbino DR, Birney E: Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome research. 2008, 18 (5): 821-829.","journal-title":"Genome research"},{"issue":"3","key":"7174_CR34","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg SL: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology. 2009, 10 (3): 25-","journal-title":"Genome Biology"},{"key":"7174_CR35","doi-asserted-by":"crossref","unstructured":"Chikhi R, Rizk G: Space-efficient and exact de Bruijn graph representation based on a Bloom filter. Algorithms for Molecular Biology. 2013, 8 (22):","DOI":"10.1186\/1748-7188-8-22"},{"key":"7174_CR36","unstructured":"2013, Variathon, [\n                    http:\/\/bioinf.dimi.uniud.it\/variathon\n                    \n                  ]"},{"issue":"2","key":"7174_CR37","doi-asserted-by":"publisher","first-page":"1003998","DOI":"10.1371\/journal.pcbi.1003998","volume":"10","author":"JF Denton","year":"2014","unstructured":"Denton JF, Lugo-Martinez J, Tucker AE, Schrider DR, Warren WC, Hahn MW: Extensive error in the number of genes inferred from draft genome assemblies. PLoS Computational Biology. 2014, 10 (2): 1003998-","journal-title":"PLoS Computational Biology"},{"key":"7174_CR38","volume-title":"TOL - Treewidth Optimization Library","author":"A Koster","year":"2012","unstructured":"Koster A: TOL - Treewidth Optimization Library. 2012"},{"issue":"16","key":"7174_CR39","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1093\/bioinformatics\/btn322","volume":"24","author":"A Morgulis","year":"2008","unstructured":"Morgulis A, Coulouris G, Raytselis Y, Madden TL, Agarwala R, Scha\u00a8 ffer AA, Koster A: Database indexing for production MegaBLAST searches. Bioinformatics (Oxford, England). 2008, 24 (16): 1757-1764.","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"1","key":"7174_CR40","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1073\/pnas.76.1.41","volume":"76","author":"R Kolodner","year":"1979","unstructured":"Kolodner R, Tewari KK: Inverted repeats in chloroplast DNA from higher plants*. Proceedings of the National Academy of Sciences of the United States of America. 1979, 76 (1): 41-45.","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-16-S14-S2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T06:26:41Z","timestamp":1548224801000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-16-S14-S2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,2]]},"references-count":40,"journal-issue":{"issue":"S14","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["7174"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-16-s14-s2","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,2]]},"assertion":[{"value":"2 October 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S2"}}