Title :
A concise necessary and sufficient condition for the existence of a galled-tree
Author_Institution :
Dept. of Comput. Sci., California Univ., Davis, CA
Abstract :
Galled-trees are a special class of graphical representation of evolutionary history that has proven amenable to efficient, polynomial-time algorithms. The goal of this paper is to construct a concise necessary and sufficient condition for the existence of a galled-tree for M, a set of binary sequences that purportedly have evolved in the presence of recombination. Both root-known and root-unknown cases are considered here
Keywords :
biology computing; evolution (biological); genetics; molecular biophysics; molecular configurations; trees (mathematics); binary sequences; efficient polynomial-time algorithms; evolutionary history; galled-tree; graphical representation; recombination; root-known cases; root-unknown cases; Binary sequences; Biological processes; Evolution (biology); Genetic mutations; History; Polynomials; Qualifications; Sufficient conditions; Testing; Tree graphs; Galled-trees; incompatibility.; quadpartition; recombination; Algorithms; Computational Biology; Evolution, Molecular; Meiosis; Models, Genetic; Phylogeny; Recombination, Genetic;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2006.15
