Bounding the Size of a Network Defined By Visibility Property

2015/10/01 by Gunawan, Andreas D. M., Zhang, Louxin
#Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.1510.00115

Abstract

Phylogenetic networks are mathematical structures for modeling and visualization of reticulation processes in the study of evolution. Galled networks, reticulation visible networks, nearly-stable networks and stable-child networks are the four classes of phylogenetic networks that are recently introduced to study the topological and algorithmic aspects of phylogenetic networks. We prove the following results. (1) A binary galled network with n leaves has at most 2(n-1) reticulation nodes. (2) A binary nearly-stable network with n leaves has at most 3(n-1) reticulation nodes. (3) A binary stable-child network with n leaves has at most 7(n-1) reticulation nodes.

Related

• Phylogenetic networks that are their own fold-ups
• Counting Phylogenetic Networks with Few Reticulation Vertices: Galled and Reticulation-Visible Networks
• Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees
• Reticulation-visible networks
• Which Phylogenetic Networks are Level-k Networks with Additional Arcs? Structure and Algorithms