{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T18:47:28Z","timestamp":1706813248302},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"S19","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>With the cost reduction of the next-generation sequencing (NGS) technologies, genomics has provided us with an unprecedented opportunity to understand fundamental questions in biology and elucidate human diseases. <jats:italic>De novo<\/jats:italic> genome assembly is one of the most important steps to reconstruct the sequenced genome. However, most <jats:italic>de novo<\/jats:italic> assemblers require enormous amount of computational resource, which is not accessible for most research groups and medical personnel.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We have developed a novel <jats:italic>de novo<\/jats:italic> assembly framework, called Tiger, which adapts to available computing resources by iteratively decomposing the assembly problem into sub-problems. Our method is also flexible to embed different assemblers for various types of target genomes. Using the sequence data from a human chromosome, our results show that Tiger can achieve much better NG50s, better genome coverage, and slightly higher errors, as compared to Velvet and SOAPdenovo, using modest amount of memory that are available in commodity computers today.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Most state-of-the-art assemblers that can achieve relatively high assembly quality need excessive amount of computing resource (in particular, memory) that is not available to most researchers to achieve high quality results. Tiger provides the only known viable path to utilize NGS <jats:italic>de novo<\/jats:italic> assemblers that require more memory than that is present in available computers. Evaluation results demonstrate the feasibility of getting better quality results with low memory footprint and the scalability of using distributed commodity computers.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-13-s19-s18","type":"journal-article","created":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T17:18:18Z","timestamp":1355937498000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["TIGER: tiled iterative genome assembler"],"prefix":"10.1186","volume":"13","author":[{"given":"Xiao-Long","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yun","family":"Heo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Izzat","family":"El Hajj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen-Mei","family":"Hwu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deming","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"issue":"2","key":"5527_CR1","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1101\/gr.079053.108","volume":"19","author":"M Chaisson","year":"2009","unstructured":"Chaisson M, Brinza D, Pevzner P: De novo fragment assembly with short mate-paired reads: Does the read length matter?. Genome Research. 2009, 19 (2): 336-346.","journal-title":"Genome Research"},{"issue":"5","key":"5527_CR2","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1101\/gr.7337908","volume":"18","author":"J Butler","year":"2008","unstructured":"Butler J, MacCallum I, Kleber M, Shlyakhter I, Belmonte M, Lander E, Nusbaum C, Jaffe D: ALLPATHS: De novo assembly of whole-genome shotgun microreads. Genome Research. 2008, 18 (5): 810-820. 10.1101\/gr.7337908.","journal-title":"Genome Research"},{"issue":"5","key":"5527_CR3","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"D Zerbino","year":"2008","unstructured":"Zerbino D, Birney E: Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Research. 2008, 18 (5): 821-829. 10.1101\/gr.074492.107.","journal-title":"Genome Research"},{"issue":"2","key":"5527_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1101\/gr.097261.109","volume":"20","author":"R Li","year":"2010","unstructured":"Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K: De novo assembly of human genomes with massively parallel short read sequencing. Genome Research. 2010, 20 (2): 265-272. 10.1101\/gr.097261.109.","journal-title":"Genome Research"},{"issue":"4","key":"5527_CR5","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1073\/pnas.1017351108","volume":"108","author":"S Gnerre","year":"2010","unstructured":"Gnerre S, MacCallum I, Przybylski D, Ribeiro F, Burton J, Walker B, Sharpe T, Hall G, Shea T, Sykes S: High-quality draft assemblies of mammalian genomes from massively parallel sequence data. Proceedings of the National Academy of Sciences. 2010, 108 (4): 1513-1518.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"6","key":"5527_CR6","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"J Simpson","year":"2009","unstructured":"Simpson J, Wong K, Jackman S, Schein J, Jones S, Birol \u0130: ABySS: A parallel assembler for short read sequence data. Genome Research. 2009, 19 (6): 1117-1123. 10.1101\/gr.089532.108.","journal-title":"Genome Research"},{"key":"5527_CR7","first-page":"1","volume-title":"Parallel & Distributed Processing (IPDPS)","author":"BG Jackson","year":"2010","unstructured":"Jackson BG, Regennitter M, Yang X, Schnable PS, Aluru S: Parallel de novo assembly of large genomes from high-throughput short reads. Parallel & Distributed Processing (IPDPS). 2010, 1-10. IEEE International Symposium on"},{"issue":"1","key":"5527_CR8","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1186\/1471-2105-12-354","volume":"12","author":"Y Liu","year":"2011","unstructured":"Liu Y, Schmidt B, Maskell D: Parallelized short read assembly of large genomes using de Bruijn graphs. BMC Bioinformatics. 2011, 12 (1): 354-10.1186\/1471-2105-12-354.","journal-title":"BMC Bioinformatics"},{"issue":"4","key":"5527_CR9","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","volume":"27","author":"T Conway","year":"2011","unstructured":"Conway T, Bromage A: Succinct data structures for assembling large genomes. Bioinformatics. 2011, 27 (4): 479-486. 10.1093\/bioinformatics\/btq697.","journal-title":"Bioinformatics"},{"key":"5527_CR10","volume-title":"Bioinformatics","author":"T Conway","year":"2012","unstructured":"Conway T, Wazny J, Bromage A, Zobel J, Beresford-Smith B: Gossamer - A Resource Efficient de novo Assembler. Bioinformatics. 2012"},{"issue":"2","key":"5527_CR11","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z Iqbal","year":"2012","unstructured":"Iqbal Z, Caccamo M, Turner I, Flicek P, McVean G: De novo assembly and genotyping of variants using colored de Bruijn graphs. Nature Genetics. 2012, 44 (2): 226-232. 10.1038\/ng.1028.","journal-title":"Nature Genetics"},{"key":"5527_CR12","volume-title":"SparseAssembler2: Sparse k-mer Graph for Memory Efficient Genome Assembly","author":"C Ye","year":"2011","unstructured":"Ye C, Cannon C, Ma Z, Yu D, Pop M: SparseAssembler2: Sparse k-mer Graph for Memory Efficient Genome Assembly. 2011"},{"issue":"3","key":"5527_CR13","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"J Simpson","year":"2011","unstructured":"Simpson J, Durbin R: Efficient de novo assembly of large genomes using compressed data structures. Genome Research. 2011, 22 (3): 549-556.","journal-title":"Genome Research"},{"issue":"3","key":"5527_CR14","doi-asserted-by":"publisher","first-page":"e17915","DOI":"10.1371\/journal.pone.0017915","volume":"6","author":"W Zhang","year":"2011","unstructured":"Zhang W, Chen J, Yang Y, Tang Y, Shang J, Shen B: A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies. PLoS ONE. 2011, 6 (3): e17915-10.1371\/journal.pone.0017915.","journal-title":"PLoS ONE"},{"issue":"9","key":"5527_CR15","doi-asserted-by":"publisher","first-page":"e24182","DOI":"10.1371\/journal.pone.0024182","volume":"6","author":"N Haiminen","year":"2011","unstructured":"Haiminen N, Kuhn D, Parida L, Rigoutsos I: Evaluation of Methods for De Novo Genome Assembly from High-Throughput Sequencing Reads Reveals Dependencies That Affect the Quality of the Results. PLoS ONE. 2011, 6 (9): e24182-10.1371\/journal.pone.0024182.","journal-title":"PLoS ONE"},{"issue":"12","key":"5527_CR16","doi-asserted-by":"publisher","first-page":"2224","DOI":"10.1101\/gr.126599.111","volume":"21","author":"D Earl","year":"2011","unstructured":"Earl D, Bradnam K, St. John J, Darling A, Lin D, Faas J, Hung On Ken Y, Vince B, Zerbino D, Diekhans M: Assemblathon 1: A competitive assessment of de novo short read assembly methods. Genome Research. 2011, 21 (12): 2224-2241. 10.1101\/gr.126599.111.","journal-title":"Genome Research"},{"issue":"15","key":"5527_CR17","doi-asserted-by":"publisher","first-page":"2031","DOI":"10.1093\/bioinformatics\/btr319","volume":"27","author":"Y Lin","year":"2011","unstructured":"Lin Y, Li J, Shen H, Zhang L, Papasian C, Deng HW: Comparative studies of de novo assembly tools for next-generation sequencing technologies. Bioinformatics. 2011, 27 (15): 2031-2037. 10.1093\/bioinformatics\/btr319.","journal-title":"Bioinformatics"},{"issue":"6","key":"5527_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","volume":"95","author":"J Miller","year":"2010","unstructured":"Miller J, Koren S, Sutton G: Assembly algorithms for next-generation sequencing data. Genomics. 2010, 95 (6): 315-327. 10.1016\/j.ygeno.2010.03.001.","journal-title":"Genomics"},{"issue":"4","key":"5527_CR19","doi-asserted-by":"publisher","first-page":"e19175","DOI":"10.1371\/journal.pone.0019175","volume":"6","author":"G Narzisi","year":"2011","unstructured":"Narzisi G, Mishra B: Comparing De Novo Genome Assembly: The Long and Short of It. PLoS ONE. 2011, 6 (4): e19175-10.1371\/journal.pone.0019175.","journal-title":"PLoS ONE"},{"issue":"3","key":"5527_CR20","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1101\/gr.131383.111","volume":"22","author":"S Salzberg","year":"2012","unstructured":"Salzberg S, Phillippy A, Zimin A, Puiu D, Magoc T, Koren S, Treangen T, Schatz M, Delcher A, Roberts M: GAGE: A critical evaluation of genome assemblies and assembly algorithms. Genome Research. 2012, 22 (3): 557-567. 10.1101\/gr.131383.111.","journal-title":"Genome Research"},{"issue":"4","key":"5527_CR21","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1038\/nmeth.1935","volume":"9","author":"M Baker","year":"2012","unstructured":"Baker M: De novo genome assembly: what every biologist should know. Nature Methods. 2012, 9 (4): 333-337. 10.1038\/nmeth.1935.","journal-title":"Nature Methods"},{"issue":"4","key":"5527_CR22","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","volume":"27","author":"M Boetzer","year":"2010","unstructured":"Boetzer M, Henkel C, Jansen H, Butler D, Pirovano W: Scaffolding pre-assembled contigs using SSPACE. Bioinformatics. 2010, 27 (4): 578-579.","journal-title":"Bioinformatics"},{"issue":"1","key":"5527_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J Sci Comput. 1998, 20 (1): 359-392. 10.1137\/S1064827595287997.","journal-title":"SIAM J Sci Comput"},{"key":"5527_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M: Identification of Common Molecular Subsequences. J Molecular Biology. 1981, 147: 195-197. 10.1016\/0022-2836(81)90087-5.","journal-title":"J Molecular Biology"},{"key":"5527_CR25","first-page":"2161","volume-title":"Computer Vision and Pattern Recognition","author":"D Nister","year":"2006","unstructured":"Nister D, Stewenius H: Scalable Recognition with a Vocabulary Tree. Computer Vision and Pattern Recognition. 2006, 2161-2168. IEEE Computer Society Conference on: 2006"},{"issue":"3","key":"5527_CR26","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg S: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology. 2009, 10 (3): R25-10.1186\/gb-2009-10-3-r25.","journal-title":"Genome Biology"},{"issue":"11","key":"5527_CR27","doi-asserted-by":"publisher","first-page":"R116","DOI":"10.1186\/gb-2010-11-11-r116","volume":"11","author":"D Kelley","year":"2010","unstructured":"Kelley D, Schatz M, Salzberg S: Quake: quality-aware detection and correction of sequencing errors. Genome Biology. 2010, 11 (11): R116-10.1186\/gb-2010-11-11-r116.","journal-title":"Genome Biology"},{"key":"5527_CR28","unstructured":"GAGE. [http:\/\/gage.cbcb.umd.edu]"},{"issue":"2","key":"5527_CR29","doi-asserted-by":"publisher","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","volume":"5","author":"S Kurtz","year":"2004","unstructured":"Kurtz S, Phillippy A, Delcher A, Smoot M, Shumway M, Antonescu C, Salzberg S: Versatile and open software for comparing large genomes. Genome Biology. 2004, 5 (2): R12-10.1186\/gb-2004-5-2-r12.","journal-title":"Genome Biology"},{"key":"5527_CR30","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-12683-3_28","volume-title":"Proceedings of the 14th Annual international conference on Research in Computational Molecular Biology:","author":"Y Peng","year":"2010","unstructured":"Peng Y, Leung H, Yiu SM, Chin F: IDBA: a practical iterative de bruijn graph de novo assembler. Proceedings of the 14th Annual international conference on Research in Computational Molecular Biology:. 2010, Springer-Verlag, 426-440. ; Lisbon, Portugal"},{"key":"5527_CR31","unstructured":"VelvetOptimizer. [http:\/\/bioinformatics.net.au\/software.velvetoptimiser.shtml]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S19-S18.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:19:37Z","timestamp":1630531177000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-S19-S18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":31,"journal-issue":{"issue":"S19","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5527"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-s19-s18","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"19 December 2012","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S18"}}