Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of t...Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures.Even though it is generally known that determining whether a network is tree-based is an NP-complete problem,one of these criteria,namely edge-basedness,can be verified in linear time.Surprisingly,the class of edgebased networks is closely related to a well-known family of graphs,namely,the class of generalized series-parallel graphs,and we explore this relationship in full detail.Additionally,we introduce further classes of tree-based networks and analyze their relationships.展开更多
基金Supported by the National Natural Science Foundation of China(11071002)the NFS of Anhui Province(11040606M14)+4 种基金the NSF of Department of Education of Anhui Province(KJ2011A195)the Program for New Century Excellent Talents in University(NCET-10-0001)the Key Project of Chinese Ministry of Education(210091)the Specialized Research Fund for the Doctoral Program of Higher Education(20103401110002)the Scientific Research Fund for Fostering Distinguished Young Scholars of Anhui University(KJJQ1001)
基金funded by the state Mecklenburg-Western Pomerania by the Landesgraduierten-Studentshipfunded by the University of Greifswald by the Bogislaw-Studentshipfunded by the German Academic Scholarship Foundation by a studentship.
文摘Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures.Even though it is generally known that determining whether a network is tree-based is an NP-complete problem,one of these criteria,namely edge-basedness,can be verified in linear time.Surprisingly,the class of edgebased networks is closely related to a well-known family of graphs,namely,the class of generalized series-parallel graphs,and we explore this relationship in full detail.Additionally,we introduce further classes of tree-based networks and analyze their relationships.
