Characterization of the existence of galled-tree networks.
In this paper, we give a complete characterization of the existence of a galled-tree network in the form of simple sufficient and necessary conditions for both root-known and root-unknown cases. As a by-product we obtain a simple algorithm for constructing galled-tree networks. We also introduce a new necessary condition for the existence of a galled-tree network similar to bi-convexity.
Gupta
Arvind
A
School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby BC V5A 1S6, Canada. arvind@mitacs.ca
Manuch
Ján
J
Zhao
Xiaohong
X
Stacho
Ladislav
L
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D005787:Gene Frequency; D006239:Haplotypes / Q000235:genetics*; D008957:Models, Genetic; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D040641:Quantitative Trait Loci / Q000235:genetics*