Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation

Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation Tsuyoshi Urata, Manato Yokoyama, Haruki Miyaji, Momoko Hayamizu This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5361648/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 05 Feb, 2026 Read the published version in Algorithms for Molecular Biology → Version 1 posted 10 You are reading this latest preprint version Abstract The C-Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired network class C. This problem arises, for example, when visualising evolutionary data, as popular methods such as Neighbor-Net are distance-based and inevitably produce undirected graphs. The complexity of C-Orientation remains open for many classes, including binary tree-child networks, and practical methods are still lacking. In this paper, we propose an exact FPT algorithm for C-Orientation that is applicable to any class C and parameterised by the reticulation number and the maximum size of minimal basic cycles, and a very fast heuristic for Tree-Child Orientation. While the state-of-the-art for C-Orientation is a simple exponential time algorithm whose computational bottleneck lies in searching for appropriate reticulation vertex placements, our methods significantly reduce this search space. Experiments show that, although our FPT algorithm is still exponential, it significantly outperforms the existing method. The heuristic runs even faster but with increasing false negatives as the reticulation number grows. Given this trade-off, we also discuss theoretical directions for improvement and biological applicability of the heuristic approach. Phylogenetic Networks Tree-Child Networks Acyclic Graph Orientation FPT Algorithm Exact Algorithm Heuristic Algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 05 Feb, 2026 Read the published version in Algorithms for Molecular Biology → Version 1 posted Editorial decision: Revision requested 29 Apr, 2025 Reviews received at journal 25 Apr, 2025 Reviewers agreed at journal 23 Apr, 2025 Reviews received at journal 22 Jan, 2025 Reviewers agreed at journal 09 Dec, 2024 Reviewers agreed at journal 05 Dec, 2024 Reviewers invited by journal 20 Nov, 2024 Editor assigned by journal 14 Nov, 2024 Submission checks completed at journal 12 Nov, 2024 First submitted to journal 30 Oct, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-5361648","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":381455429,"identity":"9d3c44ac-aebf-4286-88d8-54e42a26bb02","order_by":0,"name":"Tsuyoshi Urata","email":"","orcid":"","institution":"Department of Pure and Applied Mathematics, Graduate School of Fundamental Science and Engineering, Waseda University","correspondingAuthor":false,"prefix":"","firstName":"Tsuyoshi","middleName":"","lastName":"Urata","suffix":""},{"id":381455430,"identity":"53522acf-2374-47ed-99d4-9d27f13249f5","order_by":1,"name":"Manato Yokoyama","email":"","orcid":"","institution":"Department of Pure and Applied Mathematics, Graduate School of Fundamental Science and Engineering, Waseda University","correspondingAuthor":false,"prefix":"","firstName":"Manato","middleName":"","lastName":"Yokoyama","suffix":""},{"id":381455431,"identity":"a8513e92-d733-415c-a203-02922e7ac2cc","order_by":2,"name":"Haruki Miyaji","email":"","orcid":"","institution":"Department of Pure and Applied Mathematics, Graduate School of Fundamental Science and Engineering, Waseda University","correspondingAuthor":false,"prefix":"","firstName":"Haruki","middleName":"","lastName":"Miyaji","suffix":""},{"id":381455432,"identity":"f4588537-781d-48e9-bd0e-e2a14c2419d5","order_by":3,"name":"Momoko Hayamizu","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA1klEQVRIiWNgGAWjYBACAxjJD2awMTAwNhCrRbKBNC0gxgGoFoLAnP2M4acbBXWJm28kP/7wocyOgXk2AWsse3KMpXMM2BK33Ugzk5xxLpmBcc4BAg47kGMA1MKTuO12ghkzbxszA+OMBAJazr8x/p1jIJG4eXb6589/2+qJ0HIjxwxoi0HiBiApzdh2mBgtz8qscwwSjGfcf1Mm2XPuOA9hv5xP3nw750+dbH/P8c0ffpRVyxkSCjEGBg4DFC6P4QxCOhjYH6Dy5SUIahkFo2AUjIIRBgBXQEaD/eW3kgAAAABJRU5ErkJggg==","orcid":"","institution":"Department of Applied Mathematics, Faculty of Science and Engineering, Waseda University","correspondingAuthor":true,"prefix":"","firstName":"Momoko","middleName":"","lastName":"Hayamizu","suffix":""}],"badges":[],"createdAt":"2024-10-30 14:23:12","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5361648/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5361648/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1186/s13015-025-00282-w","type":"published","date":"2026-02-05T15:58:03+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":102234041,"identity":"63fa4942-131a-4cd7-8391-0d06bed56df2","added_by":"auto","created_at":"2026-02-09 16:05:14","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":691069,"visible":true,"origin":"","legend":"","description":"","filename":"AMBsubmit20241112.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5361648/v1_covered_1c399d0a-cbed-4e3d-908c-191f2d0a939b.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithms-for-molecular-biology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"amob","sideBox":"Learn more about [Algorithms for Molecular Biology](http://almob.biomedcentral.com/)","snPcode":"13015","submissionUrl":"https://submission.nature.com/new-submission/13015/3","title":"Algorithms for Molecular Biology","twitterHandle":"@BioMedCentral","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"BMC/SO AJ","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Phylogenetic Networks, Tree-Child Networks, Acyclic Graph Orientation, FPT Algorithm, Exact Algorithm, Heuristic Algorithm","lastPublishedDoi":"10.21203/rs.3.rs-5361648/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5361648/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"The C-Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired network class C. This problem arises, for example, when visualising evolutionary data, as popular methods such as Neighbor-Net are distance-based and inevitably produce undirected graphs. The complexity of C-Orientation remains open for many classes, including binary tree-child networks, and practical methods are still lacking. In this paper, we propose an exact FPT algorithm for C-Orientation that is applicable to any class C and parameterised by the reticulation number and the maximum size of minimal basic cycles, and a very fast heuristic for Tree-Child Orientation. While the state-of-the-art for C-Orientation is a simple exponential time algorithm whose computational bottleneck lies in searching for appropriate reticulation vertex placements, our methods significantly reduce this search space. Experiments show that, although our FPT algorithm is still exponential, it significantly outperforms the existing method. The heuristic runs even faster but with increasing false negatives as the reticulation number grows. Given this trade-off, we also discuss theoretical directions for improvement and biological applicability of the heuristic approach.","manuscriptTitle":"Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-12-05 07:43:23","doi":"10.21203/rs.3.rs-5361648/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-04-29T05:49:18+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-04-25T06:13:39+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"315425192341251568673577567910458093212","date":"2025-04-23T07:40:25+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-01-23T00:41:56+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"102996692806614661121768821005567216288","date":"2024-12-09T18:40:19+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"213017556604259848075005717227959787499","date":"2024-12-05T12:48:30+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-11-20T09:23:59+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-11-14T17:34:17+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-11-13T02:23:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithms for Molecular Biology","date":"2024-10-30T14:09:04+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithms-for-molecular-biology","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"amob","sideBox":"Learn more about [Algorithms for Molecular Biology](http://almob.biomedcentral.com/)","snPcode":"13015","submissionUrl":"https://submission.nature.com/new-submission/13015/3","title":"Algorithms for Molecular Biology","twitterHandle":"@BioMedCentral","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"BMC/SO AJ","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"e01b6aed-7cd9-4001-bb1a-454c0a206187","owner":[],"postedDate":"December 5th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2026-02-09T16:02:22+00:00","versionOfRecord":{"articleIdentity":"rs-5361648","link":"https://doi.org/10.1186/s13015-025-00282-w","journal":{"identity":"algorithms-for-molecular-biology","isVorOnly":false,"title":"Algorithms for Molecular Biology"},"publishedOn":"2026-02-05 15:58:03","publishedOnDateReadable":"February 5th, 2026"},"versionCreatedAt":"2024-12-05 07:43:23","video":"","vorDoi":"10.1186/s13015-025-00282-w","vorDoiUrl":"https://doi.org/10.1186/s13015-025-00282-w","workflowStages":[]},"version":"v1","identity":"rs-5361648","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5361648","identity":"rs-5361648","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}