Learning to Explore Tree Neighbourhoods for Phylogenetic Inference

Learning to Explore Tree Neighbourhoods for Phylogenetic Inference | 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 Learning to Explore Tree Neighbourhoods for Phylogenetic Inference Federico Julian Camerota Verdù, Andrea Gasparin, Luca Bortolussi, and 1 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6809300/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Background: Phylogenetic inference is a key challenge in computational biology, with applications ranging from evolutionary analysis to comparative genomics. The Balanced Minimum Evolution Problem (BMEP) offers a well-established formulation of this problem, but remains computationally intractable for large instances. Results: In this work, we propose a reinforcement learning (RL) framework to tackle the BMEP through local search in the space of phylogenetic trees.Our contributions are threefold: (1) we introduce an improved RL formulation tailored to the structure of phylogenetic inference in the context of the BMEP; (2) we train an RL agent capable of solving instances with up to 100 taxa; and (3) we investigate the generalization capabilities of the learned policy across different substitution models, instance sizes, and datasets.To address the limitations of relying solely on the learned policy at inference time, we integrate it into a novel search-based framework that enables effective adaptation during evaluation. Conclusions: Experimental results show that our method outperforms greedy heuristics and matches the performance of state-of-the-art algorithms for the BMEP.When tested under significant distributional shifts, we greatly reduce the gap with state-of-the-art algorithms. This demonstrates the potential of RL applications to phylogenetic inference. Phylogenetics Balanced Minimum Evolution Reinforcement Learning Online Adaptation Local Search Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-6809300","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":475959062,"identity":"6aae2166-4ac2-462c-8152-1dd6c7f0abf1","order_by":0,"name":"Federico Julian Camerota Verdù","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABeElEQVRIie3RMWuDQBQH8BMhLleyXrHRr3AipATS+FUUwcm0hUAJdOiFgl2SZivmY7iUjCcH6WL3gl1KoFMKhi4NWOgZq4jkAxTqHwe9x497zwdAkyZ/MBIBGGSPQERC61UMEkAFwt+yEswPIS2JUCVmTgS/ILwGYYXssy/ViAh/SeUaKN0G6/HlQBF9a0J3S6C2H9gq2X4NrLnMHuWz5WuHoGHIkhScGDmBq5EWYVsXfIuEswhofuzYC9+0rcW9cyUPo3edoHOThl7RmIHc7jHB1JpwQo883lHs6iI0RR1HsCsPPWYR5GIaknIWdXO6K0j4zYkaX3xycqMbGekVhKYlQbArFIRlt+DYFTlhCoacCCVplQQ6I94Yn2X6RljHQ1oQO3ww50lBUWvUm0VM9+AG02cPQUjzP8aCLUkHinZns+2H11eV2F6DpH8N21MxeNktWWcuuXoyTvuGVF0DAFr+iWr7z5bSAgdLQK0fHNhvkyZNmvzT/AA1CZWuEoL+rAAAAABJRU5ErkJggg==","orcid":"","institution":"University of Trieste","correspondingAuthor":true,"prefix":"","firstName":"Federico","middleName":"Julian Camerota","lastName":"Verdù","suffix":""},{"id":475959063,"identity":"d0939d6a-2288-4a53-bd0d-728392b91534","order_by":1,"name":"Andrea Gasparin","email":"","orcid":"","institution":"University of Trieste","correspondingAuthor":false,"prefix":"","firstName":"Andrea","middleName":"","lastName":"Gasparin","suffix":""},{"id":475959065,"identity":"98e6d275-df72-40c3-8149-94c73d97af85","order_by":2,"name":"Luca Bortolussi","email":"","orcid":"","institution":"University of Trieste","correspondingAuthor":false,"prefix":"","firstName":"Luca","middleName":"","lastName":"Bortolussi","suffix":""},{"id":475959066,"identity":"a53d3eab-8ef7-4dea-93bb-20dc3999f875","order_by":3,"name":"Lorenzo Castelli","email":"","orcid":"","institution":"University of Trieste","correspondingAuthor":false,"prefix":"","firstName":"Lorenzo","middleName":"","lastName":"Castelli","suffix":""}],"badges":[],"createdAt":"2025-06-03 09:08:29","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6809300/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6809300/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":87851183,"identity":"abc8ad37-53eb-4ea7-b78b-762bcbce9927","added_by":"auto","created_at":"2025-07-29 15:53:51","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":509310,"visible":true,"origin":"","legend":"","description":"","filename":"BMCphylorl.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6809300/v1_covered_59491f8d-b5f2-4d5a-8896-3a129adef9fb.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Learning to Explore Tree Neighbourhoods for Phylogenetic Inference","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Phylogenetics, Balanced Minimum Evolution, Reinforcement Learning, Online Adaptation, Local Search","lastPublishedDoi":"10.21203/rs.3.rs-6809300/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6809300/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003e\u003cstrong\u003eBackground:\u003c/strong\u003e Phylogenetic inference is a key challenge in computational biology, with applications ranging from evolutionary analysis to comparative genomics. The Balanced Minimum Evolution Problem (BMEP) offers a well-established formulation of this problem, but remains computationally intractable for large instances.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eResults:\u003c/strong\u003e In this work, we propose a reinforcement learning (RL) framework to tackle the BMEP through local search in the space of phylogenetic trees.Our contributions are threefold: (1) we introduce an improved RL formulation tailored to the structure of phylogenetic inference in the context of the BMEP; (2) we train an RL agent capable of solving instances with up to 100 taxa; and (3) we investigate the generalization capabilities of the learned policy across different substitution models, instance sizes, and datasets.To address the limitations of relying solely on the learned policy at inference time, we integrate it into a novel search-based framework that enables effective adaptation during evaluation.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eConclusions:\u003c/strong\u003e Experimental results show that our method outperforms greedy heuristics and matches the performance of state-of-the-art algorithms for the BMEP.When tested under significant distributional shifts, we greatly reduce the gap with state-of-the-art algorithms. This demonstrates the potential of RL applications to phylogenetic inference.\u003c/p\u003e","manuscriptTitle":"Learning to Explore Tree Neighbourhoods for Phylogenetic Inference","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-06-25 05:46:42","doi":"10.21203/rs.3.rs-6809300/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"8e0d3fbe-eedb-4f5e-9595-f4ca28865b1e","owner":[],"postedDate":"June 25th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-07-29T15:53:32+00:00","versionOfRecord":[],"versionCreatedAt":"2025-06-25 05:46:42","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6809300","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6809300","identity":"rs-6809300","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}