1
|
Xu J, Ané C. Identifiability of local and global features of phylogenetic networks from average distances. J Math Biol 2022; 86:12. [PMID: 36481927 DOI: 10.1007/s00285-022-01847-8] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/20/2021] [Revised: 11/17/2022] [Accepted: 11/22/2022] [Indexed: 12/12/2022]
Abstract
Phylogenetic networks extend phylogenetic trees to model non-vertical inheritance, by which a lineage inherits material from multiple parents. The computational complexity of estimating phylogenetic networks from genome-wide data with likelihood-based methods limits the size of networks that can be handled. Methods based on pairwise distances could offer faster alternatives. We study here the information that average pairwise distances contain on the underlying phylogenetic network, by characterizing local and global features that can or cannot be identified. For general networks, we clarify that the root and edge lengths adjacent to reticulations are not identifiable, and then focus on the class of zipped-up semidirected networks. We provide a criterion to swap subgraphs locally, such as 3-cycles, resulting in indistinguishable networks. We propose the "distance split tree", which can be constructed from pairwise distances, and prove that it is a refinement of the network's tree of blobs, capturing the tree-like features of the network. For level-1 networks, this distance split tree is equal to the tree of blobs refined to separate polytomies from blobs, and we prove that the mixed representation of the network is identifiable. The information loss is localized around 4-cycles, for which the placement of the reticulation is unidentifiable. The mixed representation combines split edges for 4-cycles, regular tree and hybrid edges from the semidirected network, and edge parameters that encode all information identifiable from average pairwise distances.
Collapse
Affiliation(s)
- Jingcheng Xu
- Department of Statistics, University of Wisconsin - Madison, Madison, WI, 53706, USA.
| | - Cécile Ané
- Department of Statistics, University of Wisconsin - Madison, Madison, WI, 53706, USA
- Department of Botany, University of Wisconsin - Madison, Madison, WI, 53706, USA
| |
Collapse
|
2
|
Counting phylogenetic networks of level 1 and 2. J Math Biol 2020; 81:1357-1395. [PMID: 33005997 DOI: 10.1007/s00285-020-01543-5] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/22/2019] [Revised: 08/29/2020] [Accepted: 09/13/2020] [Indexed: 10/23/2022]
Abstract
Phylogenetic networks generalize phylogenetic trees, and have been introduced in order to describe evolution in the case of transfer of genetic material between coexisting species. There are many classes of phylogenetic networks, which can all be modeled as families of graphs with labeled leaves. In this paper, we focus on rooted and unrooted level-k networks and provide enumeration formulas (exact and asymptotic) for rooted and unrooted level-1 and level-2 phylogenetic networks with a given number of leaves. We also prove that the distribution of some parameters of these networks (such as their number of cycles) are asymptotically normally distributed. These results are obtained by first providing a recursive description (also called combinatorial specification) of our networks, and by next applying classical methods of enumerative, symbolic and analytic combinatorics.
Collapse
|
3
|
Willems M, Lord E, Laforest L, Labelle G, Lapointe FJ, Di Sciullo AM, Makarenkov V. Using hybridization networks to retrace the evolution of Indo-European languages. BMC Evol Biol 2016; 16:180. [PMID: 27600442 PMCID: PMC5012036 DOI: 10.1186/s12862-016-0745-6] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/30/2016] [Accepted: 08/17/2016] [Indexed: 11/24/2022] Open
Abstract
Background Curious parallels between the processes of species and language evolution have been observed by many researchers. Retracing the evolution of Indo-European (IE) languages remains one of the most intriguing intellectual challenges in historical linguistics. Most of the IE language studies use the traditional phylogenetic tree model to represent the evolution of natural languages, thus not taking into account reticulate evolutionary events, such as language hybridization and word borrowing which can be associated with species hybridization and horizontal gene transfer, respectively. More recently, implicit evolutionary networks, such as split graphs and minimal lateral networks, have been used to account for reticulate evolution in linguistics. Results Striking parallels existing between the evolution of species and natural languages allowed us to apply three computational biology methods for reconstruction of phylogenetic networks to model the evolution of IE languages. We show how the transfer of methods between the two disciplines can be achieved, making necessary methodological adaptations. Considering basic vocabulary data from the well-known Dyen’s lexical database, which contains word forms in 84 IE languages for the meanings of a 200-meaning Swadesh list, we adapt a recently developed computational biology algorithm for building explicit hybridization networks to study the evolution of IE languages and compare our findings to the results provided by the split graph and galled network methods. Conclusion We conclude that explicit phylogenetic networks can be successfully used to identify donors and recipients of lexical material as well as the degree of influence of each donor language on the corresponding recipient languages. We show that our algorithm is well suited to detect reticulate relationships among languages, and present some historical and linguistic justification for the results obtained. Our findings could be further refined if relevant syntactic, phonological and morphological data could be analyzed along with the available lexical data. Electronic supplementary material The online version of this article (doi:10.1186/s12862-016-0745-6) contains supplementary material, which is available to authorized users.
Collapse
Affiliation(s)
- Matthieu Willems
- Department of Computer Science, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada
| | - Etienne Lord
- Department of Computer Science, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada.,Department of Biological Sciences, Université de Montréal, C.P. 6128 succ. Centre-Ville, Montreal, Quebec, H3C 3J7, Canada
| | - Louise Laforest
- Department of Computer Science, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada
| | - Gilbert Labelle
- Department of Mathematics, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada
| | - François-Joseph Lapointe
- Department of Biological Sciences, Université de Montréal, C.P. 6128 succ. Centre-Ville, Montreal, Quebec, H3C 3J7, Canada
| | - Anna Maria Di Sciullo
- Department of Linguistics, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada
| | - Vladimir Makarenkov
- Department of Computer Science, Université du Québec à Montréal, Case postale 8888, succursale Centre-ville, Montréal, Québec, H3C 3P8, Canada.
| |
Collapse
|