Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Dec 26;19(1):62.
doi: 10.3390/ijms19010062.

Using MOEA with Redistribution and Consensus Branches to Infer Phylogenies

Xiaoping Min  1   2 , Mouzhao Zhang  3 , Sisi Yuan  4 , Shengxiang Ge  5 , Xiangrong Liu  6 , Xiangxiang Zeng  7 , Ningshao Xia  8
Affiliations

Using MOEA with Redistribution and Consensus Branches to Infer Phylogenies

Xiaoping Min et al. Int J Mol Sci. .

Abstract

In recent years, to infer phylogenies, which are NP-hard problems, more and more research has focused on using metaheuristics. Maximum Parsimony and Maximum Likelihood are two effective ways to conduct inference. Based on these methods, which can also be considered as the optimal criteria for phylogenies, various kinds of multi-objective metaheuristics have been used to reconstruct phylogenies. However, combining these two time-consuming methods results in those multi-objective metaheuristics being slower than a single objective. Therefore, we propose a novel, multi-objective optimization algorithm, MOEA-RC, to accelerate the processes of rebuilding phylogenies using structural information of elites in current populations. We compare MOEA-RC with two representative multi-objective algorithms, MOEA/D and NAGA-II, and a non-consensus version of MOEA-RC on three real-world datasets. The result is, within a given number of iterations, MOEA-RC achieves better solutions than the other algorithms.

Keywords: consensus; genetic algorithm; many-objective optimization; phylogenies.

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Figure 1
Figure 1
Illustration of redistribution. Rectangles marked W1–Wn are populations for different weight vectors. m is the number of defaults of all the individuals. The number of individual cycles is denoted by 2 × m. m number of grey cycles are eliminated in each iteration of redistribution.
Figure 2
Figure 2
Pareto Front (PF) of the four algorithms in the three datasets at 1000 evaluation: (a) performances on rbcl_55; (b) performances on mtDNA_186; and (c) performances on ZILLA_500.
Figure 2
Figure 2
Pareto Front (PF) of the four algorithms in the three datasets at 1000 evaluation: (a) performances on rbcl_55; (b) performances on mtDNA_186; and (c) performances on ZILLA_500.
Figure 3
Figure 3
Change of ML and MP of the algorithms with various multiples of evaluation on rbcl_55: (a) Maximum Parsimony; and (b) Maximum Likelihood.
Figure 4
Figure 4
Change of MP and ML of the algorithms with various multiples of evaluation on mtDNA_186: (a) Maximum Parsimony; and (b) Maximum Likelihood.
See this image and copyright information in PMC

References

    1. Saitou N., Nei M. The neighbor-joining method: A new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 1987;4:406–425. - PubMed
    1. Gascuel O. BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data. Mol. Biol. Evol. 1997;14:685–695. doi: 10.1093/oxfordjournals.molbev.a025808. - DOI - PubMed
    1. Felsenstein J. Inferring Phylogenies. Volume 2 Sinauer Associates; Sunderland, MA, USA: 2004.
    1. Jukes T.H., Cantor C.R., Munro H. Mammalian Protein Metabolism. Elsevier; New York, NY, USA: 1969. Evolution of protein molecules; pp. 21–132.
    1. Hasegawa M., Kishino H., Yano T.-A. Dating of the human-ape splitting by a molecular clock of mitochondrial DNA. J. Mol. Evol. 1985;22:160–174. doi: 10.1007/BF02101694. - DOI - PubMed

LinkOut - more resources