{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T14:50:43Z","timestamp":1750863043476},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions.<\/jats:p>\n               <jats:p>Results: Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases.<\/jats:p>\n               <jats:p>Availability and implementation: \u00a0http:\/\/bioresearch.byu.edu\/scaffoldscaffolder.<\/jats:p>\n               <jats:p>Contact: \u00a0paulmbodily@gmail.com<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv548","type":"journal-article","created":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T08:26:51Z","timestamp":1442564811000},"page":"17-24","source":"Crossref","is-referenced-by-count":9,"title":["ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction"],"prefix":"10.1093","volume":"32","author":[{"given":"Paul M.","family":"Bodily","sequence":"first","affiliation":[{"name":"Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Stanley","family":"Fujimoto","sequence":"additional","affiliation":[{"name":"Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quinn","family":"Snell","sequence":"additional","affiliation":[{"name":"Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Ventura","sequence":"additional","affiliation":[{"name":"Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark J.","family":"Clement","sequence":"additional","affiliation":[{"name":"Computational Sciences Laboratory, Department of Computer Science, Brigham Young University, Provo, UT 84602-6576, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,9,17]]},"reference":[{"key":"2023020110214994800_btv548-B1","volume-title":"Constraint Integer Programming","author":"Achterberg","year":"2007"},{"key":"2023020110214994800_btv548-B2","doi-asserted-by":"crossref","first-page":"e1004208","DOI":"10.1371\/journal.pgen.1004208","article-title":"Validation and genotyping of multiple human polymorphic inversions mediated by inverted repeats reveals a high degree of recurrence","volume":"10","author":"Aguado","year":"2014","journal-title":"PLoS Genet."},{"key":"2023020110214994800_btv548-B3","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023020110214994800_btv548-B4","doi-asserted-by":"crossref","first-page":"2555","DOI":"10.1093\/hmg\/ddp187","article-title":"Characterization of six human disease-associated inversion polymorphisms","volume":"18","author":"Antonacci","year":"2009","journal-title":"Hum. Mol. Genet."},{"key":"2023020110214994800_btv548-B5","first-page":"177","article-title":"ARACHNE: a whole-genome shotgun assembler","volume":"12","author":"Batzoglou","year":"2002","journal-title":"Genome Res."},{"key":"2023020110214994800_btv548-B6","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","article-title":"Solving large-scale sparse semidefinite programs for combinatorial optimization","volume":"10","author":"Benson","year":"2000","journal-title":"SIAM J. Optimization"},{"key":"2023020110214994800_btv548-B7","first-page":"385","article-title":"ScaffoldScaffolder: an aggressive scaffold finishing algorithm","author":"Bodily","year":"2012"},{"key":"2023020110214994800_btv548-B8","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1101\/gr.7337908","article-title":"ALLPATHS: de novo assembly of whole-genome shotgun microreads","volume":"18","author":"Butler","year":"2008","journal-title":"Genome Res."},{"key":"2023020110214994800_btv548-B9","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1186\/1471-2105-11-345","article-title":"SOPRA: scaffolding algorithm for paired reads via statistical optimization","volume":"11","author":"Dayarian","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020110214994800_btv548-B10","first-page":"107","article-title":"A min-max cut algorithm for graph partitioning and data clustering","author":"Ding","year":"2001"},{"key":"2023020110214994800_btv548-B11","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","article-title":"SCARPA: scaffolding reads with practical algorithms","volume":"29","author":"Donmez","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020110214994800_btv548-B12","article-title":"Matching: a well-solved class of integer linear programs","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds","year":"1970"},{"key":"2023020110214994800_btv548-B13","first-page":"422","article-title":"879-approximation algorithms for MAX CUT and MAX 2SAT","author":"Goemans","year":"1994"},{"key":"2023020110214994800_btv548-B14","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","article-title":"ART: a next-generation sequencing read simulator","volume":"28","author":"Huang","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020110214994800_btv548-B15","doi-asserted-by":"crossref","DOI":"10.1109\/ICPP.2008.70","article-title":"Parallel construction of bidirected string graphs for genome assembly","author":"Jackson","year":"2008"},{"key":"2023020110214994800_btv548-B16","first-page":"319","article-title":"Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J","volume":"37","author":"Khot","year":"2007","journal-title":"Comput."},{"key":"2023020110214994800_btv548-B17","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1101\/gr.097261.109","article-title":"De\u00a0novo assembly of human genomes with massively parallel short read sequencing","volume":"20","author":"Li","year":"2010","journal-title":"Genome Res."},{"key":"2023020110214994800_btv548-B18","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/2047-217X-1-18","article-title":"SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler","volume":"1","author":"Luo","year":"2012","journal-title":"Gigascience"},{"key":"2023020110214994800_btv548-B19","author":"Makhorin","year":"2001"},{"key":"2023020110214994800_btv548-B20","doi-asserted-by":"crossref","first-page":"D1027","DOI":"10.1093\/nar\/gkt1122","article-title":"Invfest, a database integrating information of polymorphic inversions in the human genome","volume":"42","author":"Mart\u00ednez-Fundichely","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023020110214994800_btv548-B21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-540-74126-8_27","article-title":"Computability of models for sequence assembly","volume-title":"Algorithms in Bioinformatics","author":"Medvedev","year":"2007"},{"key":"2023020110214994800_btv548-B22","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1023\/A:1006491613768","article-title":"Role of inverted DNA repeats in transcriptional and post-transcriptional gene silencing","volume":"43","author":"Muskens","year":"2000","journal-title":"Plant Mol. Biol."},{"key":"2023020110214994800_btv548-B23","doi-asserted-by":"crossref","first-page":"ii79","DOI":"10.1093\/bioinformatics\/bti1114","article-title":"The fragment assembly string graph","volume":"21","author":"Myers","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020110214994800_btv548-B24","doi-asserted-by":"crossref","first-page":"i433","DOI":"10.1093\/bioinformatics\/btq366","article-title":"Integrating genome assemblies with MAIA","volume":"26","author":"Nijkamp","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020110214994800_btv548-B25","article-title":"HapMaker: synthetic haplotype generator","author":"Okuda","year":"2013"},{"key":"2023020110214994800_btv548-B26","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1101\/gr.1536204","article-title":"Hierarchical scaffolding with Bambus","volume":"14","author":"Pop","year":"2004","journal-title":"Genome Res."},{"key":"2023020110214994800_btv548-B27","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","article-title":"Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations","volume":"121","author":"Rendl","year":"2010","journal-title":"Math. Program."},{"key":"2023020110214994800_btv548-B28","doi-asserted-by":"crossref","first-page":"8929","DOI":"10.1073\/pnas.85.23.8929","article-title":"Identification and purification of a Drosophila protein that binds to the terminal 31-base-pair inverted repeats of the P transposable element","volume":"85","author":"Rio","year":"1988","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020110214994800_btv548-B29","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","article-title":"P-complete approximation problems","volume":"23","author":"Sahni","year":"1976","journal-title":"J. ACM"},{"key":"2023020110214994800_btv548-B30","doi-asserted-by":"crossref","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","article-title":"Fast scaffolding with small independent mixed integer programs","volume":"27","author":"Salmela","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020110214994800_btv548-B31","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short read assembly using De Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res."},{"key":"2023020110214994800_btv548-B32","doi-asserted-by":"crossref","first-page":"1076","DOI":"10.1038\/ng.193","article-title":"Evolutionary toggling of the MAPT 17q21. 31 inversion region","volume":"40","author":"Zody","year":"2008","journal-title":"Nat. Genet."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/1\/17\/49016378\/bioinformatics_32_1_17.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/1\/17\/49016378\/bioinformatics_32_1_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:24:50Z","timestamp":1675286690000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/1\/17\/1743932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,17]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv548","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,1,1]]},"published":{"date-parts":[[2015,9,17]]}}}