Eciency of Model-Based Complexity Method forEstimating Unrooted Multifurcate Phylogenetic Tree
Fengrong Ren

rencom@mri.tmd.ac.jp

Hiroshi Tanaka

tanaka@cim.tmd.ac.jp

Department of Bioinformatics, Tokyo Medical and Dental University
1-5-45 Yushima, Bunkyo-ku, Tokyo 113-8510, Japan

1 Introduction
In evolutionary study, many methods have been proposed so far for reconstructing phylogenetic tree
from molecular data. But it has been pointed out that multifurcate phylogenetic trees are dicult
to be correctly reconstructed by conventional methods. In order to resolve this problem, we havebeen engaged in developing a new method for reconstructing molecular phylogenetic tree, based on
the minimum complexity principle that is widely used in the inductive inference. The results ofour previous studies have proved that this method, which we call \minimum model-based complexity(MBC) method", is quite ecient in estimating rooted multifurcate tree. In this study, we make further
investigations about this method in the case that trees are unrooted by using computer simulationand statistical test. It was found that MBC method also shows good performance even in the case of
unrooted multifurcate tree and suggest that this method could be generally used for reconstructing
phylogenetic tree having arbitrary multifurcation. The details of our MBC method would be referredto our previous paper [1].

2 Computer Simulation of Unrooted Tree
We take a bifurcate and a multifurcate tree with 4 OTUs as the topology models to be compared.
The length of branch c in Fig. 1 is varied from 0.0 to 0.1 with interval 0.01 to realize the bifurcate
and multifurcate tree. That is, if c = 0 then the topology becomes multifurcate tree; if c is relatively
small comparing with a and b then the topology will be nearly multifurcate, whereas if c is statisticallysigni cantly large then the tree becomes de nitely binary. Two groups data which are assumed to be1000 bp and 3000 bp respectively are generated.
Three criteria, maximum likelihood, Akaike information criterion and model-based complexity areapplied to this simulation to select whether the trees are bifurcate or multifurcate. When c = 0 or
nearly 0, both AIC and MBC are supposed to select the multifurcate tree, but they become more
inclined to select the bifurcate tree as the true value of branch length c increases. At some c value,
the frequencies to select multifurcate and bifurcate tree become almost equal. We denote this valueof c by cAIC (0:5) or cMBC (0:5).
The results by complexity criteria are examined by using statistic test. Since even if the true valueof the branch c is 0, the estimated value c^ would distribute around 0. Here the boundary value of 95%
con dence interval of the estimation is considered as the threshold c (0:05) to accept or reject c = 0:(1) if the estimation c^ exceeds the threshold c (0:05), which means the node is bifurcate. (2) if theestimation c^ is below the threshold c (0:05), which means that the node is multifurcate.
Since the cAIC (0:5) and cMBC (0:5) values in the complexity criterion approach behave the samerole as the thresholds in statistical test, we can compare the c (0:05) with cAIC (0:5) and cMBC (0:5)
to clarify the features of these complexity criteria in selecting the tree topology.
342dbbccdaaee

Bifurcate tree

Multifurcate tree

Figure 1: Bifurcate and multifurcate tree models used for computer simulation.

900

1000
900

800

800

700

700

600

600

1000

500

500

400

400

300

n=3000bp300

n=1000bp

200
100

200
100

00.02

0.04

0.06

0.08

00.1

0.02

0.04

0.06

0.08

0.1

Figure 2: Change of the selection ratio when c is varied. Ordinate denotes the frequency that bifurcate
tree is selected among simulated 1000 samples. Abscissa denotes the true c value used in generation ofthe data. Dotted line indicates ML method, whereas thin line and thick line indicate AIC and MBC
method, respectively.

3 Results and Conclusion
The AIC method shows good correspondence with statistical test based on simulated data, but in thissimulation, exactly the same evolution model fPij (u)g is used in generation of the data and estimationof branch lengths. In real situations, we should also estimate the evolution model from the data, which
certainly produces estimation errors. If we take this e ect into account in determining the con dence
interval of the estimation, the threshold values of statistical test will becomes larger. Hence we would
say that AIC method, needless to say ML method, overestimates the complexity of tree topology
to prefer the bifurcate tree. On the contrary, the underestimation in MBC method is not fatal but
much more appropriate when the unpredictable sources of estimation variation in the modeling areconsidered.

References[1] Tanaka, H., Ren, F., Okayama, T., and Gojobori, T., Inference of Molecular Phylogenetic Tree
Based on Minimum Model Based Complexity Method, Proc. 5th Intl. Conf. on Intelligent Systemsfor Molecular Biology, 319{328, 1997.

343