{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:37Z","timestamp":1740144517312,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the \u201cscaffold graph\u201d.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We provide some NP-hardness and inapproximability results on this problem. We also adapt a greedy approximation algorithm on complete graphs so that it works on a special class aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>Tests on a set of simulated instances show that our algorithm provides better results than the version on complete graphs.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-022-00223-x","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T10:15:04Z","timestamp":1667038504000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On a greedy approach for genome scaffolding"],"prefix":"10.1186","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4203-5140","authenticated-orcid":false,"given":"Tom","family":"Davot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohan","family":"Foss\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"issue":"2","key":"223_CR1","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1038\/nprot.2016.182","volume":"12","author":"ER Mardis","year":"2017","unstructured":"Mardis ER. DNA sequencing technologies: 2006\u20132016. Nat Protoc. 2017;12(2):213\u20138.","journal-title":"Nat Protoc"},{"issue":"1","key":"223_CR2","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1186\/s12864-017-3927-8","volume":"18","author":"JR Miller","year":"2017","unstructured":"Miller JR, Zhou P, Mudge J, Gurtowski J, Lee H, Ramaraj T, Walenz BP, Liu J, Stupar RM, Denny R, Song L, Singh N, Maron LG, McCouch SR, McCombie WR, Schatz MC, Tiffin P, Young ND, Silverstein KAT. Hybrid assembly with long and short reads improves discovery of gene family expansions. BMC Genomics. 2017;18(1):541.","journal-title":"BMC Genomics"},{"doi-asserted-by":"publisher","unstructured":"Mandric I, Lindsay J, M\u0103ndoiu II, Zelikovsky A. Scaffolding algorithms, Chap 5. In: M\u0103ndoiu I, Zelikovsky A, editors. Computational methods for next generation sequencing data analysis. NJ: John Wiley & Sons Ltd; 2016. p. 105\u2013131. https:\/\/doi.org\/10.1002\/9781119272182.ch5","key":"223_CR3","DOI":"10.1002\/9781119272182.ch5"},{"doi-asserted-by":"publisher","unstructured":"Chateau A, Giroudeau R. Complexity and polynomial-time approximation algorithms around the scaffolding problem. In: Dediu AH, Mart\u00edn-Vide C, Truthe B, editors.  Algorithms for Computational Biology. AlCoB 2014. Lecture Notes in Computer Science. 2014; p. 47\u201358. https:\/\/doi.org\/10.1007\/978-3-319-07953-0_4","key":"223_CR4","DOI":"10.1007\/978-3-319-07953-0_4"},{"key":"223_CR5","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. Theor Comput Sci. 2015;595:92\u2013106.","journal-title":"Theor Comput Sci"},{"key":"223_CR6","first-page":"17","volume-title":"Front Neurorobot","author":"Z-Z Chen","year":"2016","unstructured":"Chen Z-Z, Harada Y, Machida E, Guo F, Wang L. Better approximation algorithms for scaffolding problems. In: Zhu D, Bereg S, editors. Front Neurorobot. Cham: Springer; 2016. p. 17\u201328."},{"issue":"Suppl 14","key":"223_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1471-2105-16-S14-S2","volume":"16","author":"M Weller","year":"2015","unstructured":"Weller M, Chateau A, Giroudeau R. Exact approaches for scaffolding. BMC Bioinform. 2015;16(Suppl 14):2.","journal-title":"BMC Bioinform"},{"doi-asserted-by":"publisher","unstructured":"Weller M, Chateau A, Giroudeau R. On the complexity of scaffolding problems: from cliques to sparse graphs. In: Lu Z, Kim D, Wu W, Li W, Du DZ, editors. Combinatorial optimization and applications, Lecture Notes in Computer Science. Cham: Springer; 2015. p. 409\u2013423. https:\/\/doi.org\/10.1007\/978-3-319-26626-8_30","key":"223_CR8","DOI":"10.1007\/978-3-319-26626-8_30"},{"key":"223_CR9","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-319-48749-6_22","volume-title":"Combinatorial optimization and applications","author":"C Dallard","year":"2016","unstructured":"Dallard C, Weller M, Chateau A, Giroudeau R. Instance guaranteed ratio on greedy heuristic for genome scaffolding. In: Chan T-HH, Li M, Wang L, editors. Combinatorial optimization and applications. Cham: Springer; 2016. p. 294\u2013308."},{"issue":"6","key":"223_CR10","doi-asserted-by":"publisher","first-page":"1771","DOI":"10.1007\/s00453-018-0405-x","volume":"80","author":"M Weller","year":"2018","unstructured":"Weller M, Chateau A, Dallard C, Giroudeau R. Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases. Algorithmica. 2018;80(6):1771\u2013803.","journal-title":"Algorithmica"},{"issue":"21","key":"223_CR11","doi-asserted-by":"publisher","first-page":"10994","DOI":"10.1093\/nar\/gkz841","volume":"47","author":"OK T\u00f8rresen","year":"2019","unstructured":"T\u00f8rresen OK, Star B, Mier P, Andrade-Navarro MA, Bateman A, Jarnot P, Gruca A, Grynberg M, Kajava AV, Promponas VJ, Anisimova M, Jakobsen KS, Linke D. Tandem repeats lead to sequence assembly errors and impose multi-level challenges for genome and protein databases. Nucleic Acids Res. 2019;47(21):10994\u20131006.","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"223_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.7155\/jgaa.00207","volume":"14","author":"VV Lozin","year":"2010","unstructured":"Lozin VV, Milanic M. On the maximum independent set problem in subclasses of planar graphs. J Graph Algorithms Appl. 2010;14(2):269\u201386.","journal-title":"J Graph Algorithms Appl"},{"unstructured":"Orponen P, Mannila H. On approximation preserving reductions: complete problems and robust measures (revised version). 1987. https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.64.7246","key":"223_CR13"},{"issue":"2","key":"223_CR14","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.tcs.2005.03.007","volume":"339","author":"C Bazgan","year":"2005","unstructured":"Bazgan C, Escoffier B, Paschos VT. Completeness in standard and differential approximation classes: Poly-(d)apx- and (d)ptas-completeness. Theor Comput Sci. 2005;339(2):272\u201392.","journal-title":"Theor Comput Sci"},{"unstructured":"Weller M, Chateau A, Giroudeau R, Poss M. Scaffolding with repeated contigs using flow formulations","key":"223_CR15"},{"unstructured":"CPLEX, IBM ILOG. V12. 1: User\u2019s Manual for CPLEX. Int Bus Mach Corporation. 2009;46(53):157.","key":"223_CR16"},{"issue":"16","key":"223_CR17","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 GT, Abecasis GR, Durbin R. The sequence alignment\/map format and SAMtools. Bioinformatics. 2009;25(16):2078\u20139.","journal-title":"Bioinformatics"},{"key":"223_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1748-7188-8-22","volume":"8","author":"R Chikhi","year":"2012","unstructured":"Chikhi R, Rizk G. Space-efficient and exact de Bruijn graph representation based on a bloom filter. Algorithms Mol Biol. 2012;8:22. https:\/\/doi.org\/10.1186\/1748-7188-8-22.","journal-title":"Algorithms Mol Biol"},{"issue":"5","key":"223_CR19","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\u201395.","journal-title":"Bioinformatics"},{"key":"223_CR20","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2014-15-3-r42","author":"M Hunt","year":"2014","unstructured":"Hunt M, Newbold C, Berriman M, Otto T. A comprehensive evaluation of assembly scaffolding tools. Genome Biol. 2014. https:\/\/doi.org\/10.1186\/gb-2014-15-3-r42.","journal-title":"Genome Biol."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00223-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-022-00223-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00223-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T10:16:45Z","timestamp":1667038605000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-022-00223-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,29]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["223"],"URL":"https:\/\/doi.org\/10.1186\/s13015-022-00223-x","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2022,10,29]]},"assertion":[{"value":"19 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"16"}}