Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks

Autor: Leo van Iersel, Vincent Moulton, Remie Janssen, Mark Jones, Yukihiro Murakami
Rok vydání: 2019
Předmět:
0301 basic medicine
Computer science
General Mathematics
Immunology
Tree-child networks
General Biochemistry
Genetics and Molecular Biology
Evolution
Molecular
Combinatorics
03 medical and health sciences
0302 clinical medicine
Reticulate
FOS: Mathematics
Mathematics - Combinatorics
Reticulate-edge-deleted subnetworks
Phylogeny
General Environmental Science
Pharmacology
Phylogenetic network
Models
Genetic
Phylogenetic tree
General Neuroscience
Node (networking)
Computational Biology
Biconnected component
Mathematical Concepts
Tree (graph theory)
Tree node
030104 developmental biology
Network encoding
Computational Theory and Mathematics
030220 oncology & carcinogenesis
Original Article
Combinatorics (math.CO)
Enhanced Data Rates for GSM Evolution
General Agricultural and Biological Sciences
Algorithms
Zdroj: Bulletin of Mathematical Biology, 81(10)
Bulletin of Mathematical Biology
Bulletin of Mathematical Biology, 81, 3823-3863
ISSN: 1522-9602
0092-8240
DOI: 10.1007/s11538-019-00641-w
Popis: Network reconstruction lies at the heart of phylogenetic research. Two well studied classes of phylogenetic networks include tree-child networks and level-$k$ networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-$k$ network, the maximum number of reticulations contained in a biconnected component is $k$. Here, we show that level-$k$ tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if $k\geq 2$. Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with $k$ reticulations.
Comment: 30 pages, 19 figures
Databáze: OpenAIRE
Externí odkaz: