{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:45:43Z","timestamp":1740181543998,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s42979-022-01198-7","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T11:03:33Z","timestamp":1653563013000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Orienting Ordered Scaffolds: Complexity and Algorithms"],"prefix":"10.1007","volume":"3","author":[{"given":"Sergey","family":"Aganezov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Avdeyev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikita","family":"Alexeev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongwu","family":"Rong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5140-8095","authenticated-orcid":false,"given":"Max A.","family":"Alekseyev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"1198_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-319-38782-6_20","volume-title":"Multi-genome scaffold co-assembly based on the analysis of gene orders and genomic repeats","author":"S Aganezov","year":"2016","unstructured":"Aganezov S, Alekseyev MA. In: Bourgeois A, Skums P, Wan X, Zelikovsky A, editors. Multi-genome scaffold co-assembly based on the analysis of gene orders and genomic repeats, vol. 9683. Cham: Springer; 2016. pp. 237\u201349. https:\/\/doi.org\/10.1007\/978-3-319-38782-6_20."},{"issue":"15","key":"1198_CR2","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1186\/s12859-017-1919-y","volume":"18","author":"SS Aganezov","year":"2017","unstructured":"Aganezov SS, Alekseyev MA. CAMSA: a tool for comparative analysis and merging of scaffold assemblies. BMC Bioinform. 2017;18(15):496. https:\/\/doi.org\/10.1186\/s12859-017-1919-y.","journal-title":"BMC Bioinform"},{"issue":"Suppl 10","key":"1198_CR3","doi-asserted-by":"publisher","first-page":"S11","DOI":"10.1186\/1471-2164-16-S10-S11","volume":"16","author":"Y Anselmetti","year":"2015","unstructured":"Anselmetti Y, Berry V, Chauve C, Chateau A, Tannier E, B\u00e9rard S. Ancestral gene synteny reconstruction improves extant species scaffolding. BMC Genom. 2015;16(Suppl 10):S11. https:\/\/doi.org\/10.1186\/1471-2164-16-S10-S11.","journal-title":"BMC Genom."},{"key":"1198_CR4","unstructured":"Assour LA, Emrich SJ. Multi-genome synteny for assembly improvement multi-genome synteny for assembly improvement. In: Proceedings of 7th international conference on bioinformatics and computational biology, 2015. pp. 193\u2013199"},{"issue":"3","key":"1198_CR5","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1089\/cmb.2015.0160","volume":"23","author":"P Avdeyev","year":"2016","unstructured":"Avdeyev P, Jiang S, Aganezov S, Hu F, Alekseyev MA. Reconstruction of ancestral genomes in presence of gene gain and loss. J Comput Biol. 2016;23(3):150\u201364. https:\/\/doi.org\/10.1089\/cmb.2015.0160.","journal-title":"J Comput Biol"},{"issue":"5","key":"1198_CR6","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1089\/cmb.2012.0021","volume":"19","author":"A Bankevich","year":"2012","unstructured":"Bankevich A, Nurk S, Antipov D, Gurevich AA, Dvorkin M, Kulikov AS, Lesin VM, Nikolenko SI, Pham S, Prjibelski AD, Pyshkin AV, Sirotkin AV, Vyahhi N, Tesler G, Alekseyev MA, Pevzner PA. SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J Comput Biol. 2012;19(5):455\u201377. https:\/\/doi.org\/10.1089\/cmb.2012.0021.","journal-title":"J Comput Biol"},{"issue":"7","key":"1198_CR7","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1038\/nbt.2288","volume":"30","author":"A Bashir","year":"2012","unstructured":"Bashir A, Klammer AA, Robins WP, Chin CS, Webster D, Paxinos E, Hsu D, Ashby M, Wang S, Peluso P, Sebra R, Sorenson J, Bullard J, Yen J, Valdovino M, Mollova E, Luong K, Lin S, LaMay B, Joshi A, Rowe L, Frace M, Tarr CL, Turnsek M, Davis BM, Kasarskis A, Mekalanos JJ, Waldor MK, Schadt EE. A hybrid approach for the automated finishing of bacterial genomes. Nat Biotechnol. 2012;30(7):701\u20137. https:\/\/doi.org\/10.1038\/nbt.2288.","journal-title":"Nat Biotechnol"},{"issue":"2","key":"1198_CR8","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0377-2217(02)00299-0","volume":"147","author":"C Bazgan","year":"2003","unstructured":"Bazgan C, Paschos VT. Differential approximation for optimal satisfiability and related problems. Eur J Oper Res. 2003;147(2):397\u2013404. https:\/\/doi.org\/10.1016\/S0377-2217(02)00299-0.","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1198_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/1008861.1008865","volume":"12","author":"JL Bentley","year":"1980","unstructured":"Bentley JL, Haken D, Saxe JB. A general method for solving divide-and-conquer recurrences. ACM SIGACT News. 1980;12(3):36\u201344. https:\/\/doi.org\/10.1145\/1008861.1008865.","journal-title":"ACM SIGACT News"},{"issue":"1","key":"1198_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1093\/bioinformatics\/btv548","volume":"32","author":"PM Bodily","year":"2015","unstructured":"Bodily PM, Fujimoto MS, Snell Q, Ventura D, Clement MJ. ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction. Bioinformatics. 2015;32(1):17\u201324. https:\/\/doi.org\/10.1093\/bioinformatics\/btv548.","journal-title":"Bioinformatics"},{"issue":"4","key":"1198_CR11","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\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/btq683.","journal-title":"Bioinformatics"},{"issue":"1","key":"1198_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1186\/1471-2105-15-211","volume":"15","author":"M Boetzer","year":"2014","unstructured":"Boetzer M, Pirovano W. SSPACE-LongRead: scaffolding bacterial draft genomes using long read sequence information. BMC Bioinform. 2014;15(1):211. https:\/\/doi.org\/10.1186\/1471-2105-15-211.","journal-title":"BMC Bioinform"},{"issue":"12","key":"1198_CR13","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1038\/nbt.2727","volume":"31","author":"JN Burton","year":"2013","unstructured":"Burton JN, Adey A, Patwardhan RP, Qiu R, Kitzman JO, Shendure J. Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions. Nat Biotechnol. 2013;31(12):1119\u201325. https:\/\/doi.org\/10.1038\/nbt.2727.","journal-title":"Nat Biotechnol"},{"key":"1198_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.03.042","author":"ZZ Chen","year":"2017","unstructured":"Chen ZZ, Harada Y, Guo F, Wang L. Approximation algorithms for the scaffolding problem and its generalizations. Theor Comput Sci. 2017. https:\/\/doi.org\/10.1016\/j.tcs.2017.03.042.","journal-title":"Theor Comput Sci."},{"key":"1198_CR15","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 Bioinform. 2010;11:345. https:\/\/doi.org\/10.1186\/1471-2105-11-345.","journal-title":"BMC Bioinform"},{"issue":"2","key":"1198_CR16","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1016\/j.ejor.2005.04.057","volume":"181","author":"B Escoffier","year":"2007","unstructured":"Escoffier B, Paschos VT. Differential approximation of min sat, max sat and related problems. Eur J Oper Res. 2007;181(2):620\u201333. https:\/\/doi.org\/10.1016\/j.ejor.2005.04.057.","journal-title":"Eur J Oper Res"},{"issue":"11","key":"1198_CR17","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","volume":"18","author":"S Gao","year":"2011","unstructured":"Gao S, Sung WK, Nagarajan N. Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences. J Comput Biol. 2011;18(11):1681\u201391. https:\/\/doi.org\/10.1089\/cmb.2011.0170.","journal-title":"J Comput Biol"},{"key":"1198_CR18","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness, vol. 58. San Francisco: Freeman; 1979."},{"issue":"3","key":"1198_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Stockmeyer L. Some simplified NP-complete graph problems. Theor Comput Sci. 1976;1(3):237\u201367.","journal-title":"Theor Comput Sci"},{"issue":"11","key":"1198_CR20","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\u201337. https:\/\/doi.org\/10.1093\/bioinformatics\/bts175.","journal-title":"Bioinformatics"},{"key":"1198_CR21","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 TD. A comprehensive evaluation of assembly scaffolding tools. Genome Biol. 2014. https:\/\/doi.org\/10.1186\/gb-2014-15-3-r42.","journal-title":"Genome Biol"},{"issue":"5","key":"1198_CR22","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1101\/gr.213652.116","volume":"27","author":"WB Jiao","year":"2017","unstructured":"Jiao WB, Garcia Accinelli G, Hartwig B, Kiefer C, Baker D, Severing E, Willing EM, Piednoel M, Woetzel S, Madrid-Herrero E, Huettel B, H\u00fcmann U, Reinhard R, Koch MA, Swan D, Clavijo B, Coupland G, Schneeberger K. Improving and correcting the contiguity of long-read genome assemblies of three plant species using optical mapping and chromosome conformation capture data. Genome Res. 2017;27(5):116. https:\/\/doi.org\/10.1101\/gr.213652.116.","journal-title":"Genome Res"},{"issue":"1\u20132","key":"1198_CR23","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu JD, Myers EW. Combinatorial algorithms for DNA sequence assembly. Algorithmica. 1995;13(1\u20132):7\u201351. https:\/\/doi.org\/10.1007\/BF01188580.","journal-title":"Algorithmica"},{"key":"1198_CR24","doi-asserted-by":"publisher","DOI":"10.1101\/088435","author":"M Kolmogorov","year":"2016","unstructured":"Kolmogorov M, Armstrong J, Raney BJ, Streeter I, Dunn M, Yang F, Odom D, Flicek P, Keane T, Thybert D, Paten B, Pham S. Chromosome assembly of large and complex genomes using multiple references. Preprint bioRxiv. 2016. https:\/\/doi.org\/10.1101\/088435.","journal-title":"Preprint bioRxiv"},{"issue":"21","key":"1198_CR25","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\u201371. https:\/\/doi.org\/10.1093\/bioinformatics\/btr520.","journal-title":"Bioinformatics"},{"issue":"19","key":"1198_CR26","doi-asserted-by":"publisher","first-page":"3207","DOI":"10.1093\/bioinformatics\/btv280","volume":"31","author":"KK Lam","year":"2015","unstructured":"Lam KK, Labutti K, Khalak A, Tse D. FinisherSC: a repeat-aware tool for upgrading de novo assembly using long reads. Bioinformatics. 2015;31(19):3207\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/btv280.","journal-title":"Bioinformatics"},{"issue":"1","key":"1198_CR27","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/2047-217X-1-18","volume":"1","author":"R Luo","year":"2012","unstructured":"Luo R, Liu B, Xie Y, Li Z, Huang W, Yuan J, Wang J. SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler. Gigascience. 2012;1(1):18. https:\/\/doi.org\/10.1186\/2047-217X-1-18.","journal-title":"Gigascience"},{"issue":"10","key":"1198_CR28","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1093\/bioinformatics\/btn102","volume":"24","author":"N Nagarajan","year":"2008","unstructured":"Nagarajan N, Read TD, Pop M. Scaffolding and validation of bacterial genome assemblies using optical restriction maps. Bioinformatics. 2008;24(10):1229\u201335. https:\/\/doi.org\/10.1093\/bioinformatics\/btn102.","journal-title":"Bioinformatics"},{"issue":"1","key":"1198_CR29","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1101\/gr.1536204","volume":"14","author":"M Pop","year":"2004","unstructured":"Pop M, Kosack DS, Salzberg SL. Hierarchical scaffolding with Bambus. Genome Res. 2004;14(1):149\u201359. https:\/\/doi.org\/10.1101\/gr.1536204.","journal-title":"Genome Res"},{"issue":"3","key":"1198_CR30","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1101\/gr.193474.115","volume":"26","author":"NH Putnam","year":"2016","unstructured":"Putnam NH, O\u2019Connell BL, Stites JC, Rice BJ, Blanchette M, Calef R, Troll CJ, Fields A, Hartley PD, Sugnet CW, Haussler D, Rokhsar DS, Green RE. Chromosome-scale shotgun assembly using an in vitro method for long-range linkage. Genome Res. 2016;26(3):342\u201350. https:\/\/doi.org\/10.1101\/gr.193474.115.","journal-title":"Genome Res"},{"key":"1198_CR31","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms14953","author":"S Reyes-Chin-Wo","year":"2017","unstructured":"Reyes-Chin-Wo S, Wang Z, Yang X, Kozik A, Arikit S, Song C, Xia L, Froenicke L, Lavelle DO, Truco MJ, Xia R, Zhu S, Xu C, Xu H, Xu X, Cox K, Korf I, Meyers BC, Michelmore RW. Genome assembly with in vitro proximity ligation data and whole-genome triplication in lettuce. Nat Commun. 2017. https:\/\/doi.org\/10.1038\/ncomms14953.","journal-title":"Nat Commun"},{"issue":"6","key":"1198_CR32","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"JT Simpson","year":"2009","unstructured":"Simpson JT, Wong K, Jackman SD, Schein JE, Jones SJ, Birol I. ABySS: a parallel assembler for short read sequence data. Genome Res. 2009;19(6):1117\u201323. https:\/\/doi.org\/10.1101\/gr.089532.108.","journal-title":"Genome Res"},{"issue":"1","key":"1198_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13059-014-0573-1","volume":"16","author":"H Tang","year":"2015","unstructured":"Tang H, Zhang X, Miao C, Zhang J, Ming R, Schnable JC, Schnable PS, Lyons E, Lu J. ALLMAPS: robust scaffold ordering based on multiple maps. Genome Biol. 2015;16(1):3. https:\/\/doi.org\/10.1186\/s13059-014-0573-1.","journal-title":"Genome Biol"},{"issue":"1","key":"1198_CR34","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1186\/s13742-015-0076-3","volume":"4","author":"RL Warren","year":"2015","unstructured":"Warren RL, Yang C, Vandervalk BP, Behsaz B, Lagman A, Jones SJM, Birol I. LINKS: scalable, alignment-free scaffolding of draft genomes with long reads. GigaScience. 2015;4(1):35. https:\/\/doi.org\/10.1186\/s13742-015-0076-3.","journal-title":"GigaScience"},{"issue":"1","key":"1198_CR35","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1093\/bioinformatics\/btm542","volume":"24","author":"AV Zimin","year":"2008","unstructured":"Zimin AV, Smith DR, Sutton G, Yorke JA. Assembly reconciliation. Bioinformatics. 2008;24(1):42\u20135. https:\/\/doi.org\/10.1093\/bioinformatics\/btm542.","journal-title":"Bioinformatics"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01198-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01198-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01198-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:02:44Z","timestamp":1656003764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01198-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1198"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01198-7","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"20 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 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":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"308"}}