Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming
Abstract Neighbor‐net is a widely used network reconstructing method that approximates pairwise distances between taxa by a circular phylogenetic network. We present Lpnet, a variant of Neighbor‐net. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-05-01
|
| Series: | Methods in Ecology and Evolution |
| Subjects: | |
| Online Access: | https://doi.org/10.1111/2041-210X.14086 |
| _version_ | 1797767022855061504 |
|---|---|
| author | Mengzhen Guo Stefan Grünewald |
| author_facet | Mengzhen Guo Stefan Grünewald |
| author_sort | Mengzhen Guo |
| collection | DOAJ |
| description | Abstract Neighbor‐net is a widely used network reconstructing method that approximates pairwise distances between taxa by a circular phylogenetic network. We present Lpnet, a variant of Neighbor‐net. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear programming to compute an optimal circular ordering that agrees with all tree splits. This approach achieves an improved approximation of the input distance for the clear majority of experiments that we have run for simulated and real data. We release an implementation in R that can handle up to 94 taxa and usually needs about 1 min on a standard computer for 80 taxa. For larger taxa sets, we include a top‐down heuristic which also tends to perform better than Neighbor‐net. Our Lpnet provides an alternative to Neighbor‐net and performs better in most cases. We anticipate Lpent will be useful to generate phylogenetic hypotheses. |
| first_indexed | 2024-03-12T20:33:45Z |
| format | Article |
| id | doaj.art-edb15c9063e84bc398d19cd5c700553a |
| institution | Directory Open Access Journal |
| issn | 2041-210X |
| language | English |
| last_indexed | 2024-03-12T20:33:45Z |
| publishDate | 2023-05-01 |
| publisher | Wiley |
| record_format | Article |
| series | Methods in Ecology and Evolution |
| spelling | doaj.art-edb15c9063e84bc398d19cd5c700553a2023-08-01T18:55:36ZengWileyMethods in Ecology and Evolution2041-210X2023-05-011451276128610.1111/2041-210X.14086Lpnet: Reconstructing phylogenetic networks from distances using integer linear programmingMengzhen Guo0Stefan Grünewald1Shanghai Institute of Nutrition and Health University of Chinese Academy of Sciences Chinese Academy of Sciences Shanghai People's Republic of ChinaShanghai Institute of Nutrition and Health University of Chinese Academy of Sciences Chinese Academy of Sciences Shanghai People's Republic of ChinaAbstract Neighbor‐net is a widely used network reconstructing method that approximates pairwise distances between taxa by a circular phylogenetic network. We present Lpnet, a variant of Neighbor‐net. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear programming to compute an optimal circular ordering that agrees with all tree splits. This approach achieves an improved approximation of the input distance for the clear majority of experiments that we have run for simulated and real data. We release an implementation in R that can handle up to 94 taxa and usually needs about 1 min on a standard computer for 80 taxa. For larger taxa sets, we include a top‐down heuristic which also tends to perform better than Neighbor‐net. Our Lpnet provides an alternative to Neighbor‐net and performs better in most cases. We anticipate Lpent will be useful to generate phylogenetic hypotheses.https://doi.org/10.1111/2041-210X.14086circular split systemsdistance‐based phylogeneticsinteger linear programmingneighbor‐netphylogenetic networks |
| spellingShingle | Mengzhen Guo Stefan Grünewald Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming Methods in Ecology and Evolution circular split systems distance‐based phylogenetics integer linear programming neighbor‐net phylogenetic networks |
| title | Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming |
| title_full | Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming |
| title_fullStr | Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming |
| title_full_unstemmed | Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming |
| title_short | Lpnet: Reconstructing phylogenetic networks from distances using integer linear programming |
| title_sort | lpnet reconstructing phylogenetic networks from distances using integer linear programming |
| topic | circular split systems distance‐based phylogenetics integer linear programming neighbor‐net phylogenetic networks |
| url | https://doi.org/10.1111/2041-210X.14086 |
| work_keys_str_mv | AT mengzhenguo lpnetreconstructingphylogeneticnetworksfromdistancesusingintegerlinearprogramming AT stefangrunewald lpnetreconstructingphylogeneticnetworksfromdistancesusingintegerlinearprogramming |