A topological transformation in evolutionary tree search methods based on maximum likelihood combining p-ECR and neighbor joining.
BACKGROUND
Inference of evolutionary trees using the maximum likelihood principle is NP-hard. Therefore, all practical methods rely on heuristics. The topological transformations often used in heuristics are Nearest Neighbor Interchange (NNI), Subtree Prune and Regraft (SPR) and Tree Bisection and Reconnection (TBR). However, these topological transformations often fall easily into local optima, since there are not many trees accessible in one step from any given tree. Another more exhaustive topological transformation is p-Edge Contraction and Refinement (p-ECR). However, due to its high computation complexity, p-ECR has rarely been used in practice.


RESULTS
To make the p-ECR move more efficient, this paper proposes a new method named p-ECRNJ. The main idea of p-ECRNJ is to use neighbor joining (NJ) to refine the unresolved nodes produced in p-ECR.


CONCLUSIONS
Experiments with real datasets show that p-ECRNJ can find better trees than the best known maximum likelihood methods so far and can efficiently improve local topological transforms in reasonable time.
Department of Computer Science and Technology, Harbin Institute of Technology, Harbin, 150001, PR China. maozuguo@hit.edu.cn
Mao-Zu
MZ
Guo
Jian-Fu
JF
Li
Yang
Y
Liu
D000465:Algorithms; D001483:Base Sequence; D005075:Biological Evolution; D003198:Computer Simulation; D019143:Evolution, Molecular; D016013:Likelihood Functions; D008958:Models, Molecular; D008969:Molecular Sequence Data; D010802:Phylogeny; D017422:Sequence Analysis, DNA / Q000379:methods*