Edge Ratchet and Simulated Annealing to Improve RF Score of the Supertree of Life
Abstract
Constructing the Supertree of Life can provide crucially valuable knowledge to address
many critical contemporary challenges such as fighting diseases, improving global
agriculture, and protecting ecosystems to name a few. However, building such a tree is
among the most complicated and challenging scientific problems. In the case of biological
data, the true species tree is not available. Hence, the accuracy of the supertree is usually
evaluated based on its similarity to the given source input trees.
In this work, we aim at improving the accuracy of the supertree in terms of its cumulative
Robinson Foulds (RF) distance to the source trees. This problem is NP-hard. Therefore,
we have to resort to heuristic algorithms. We have two main contributions in this
work. First, we propose a new technique, Edge Ratchet, which is used in a hill-climbing
based algorithm to deal with local optimum problem. Second, we develop a Simulated
Annealing algorithm to minimize total RF distance of the supertree to the source trees.
Our results demonstrate that these two algorithms are able to improve the accuracy of the
best existing supertree algorithms with regard to RF distance.
Citation
Manshouri, Reza (2017). Edge Ratchet and Simulated Annealing to Improve RF Score of the Supertree of Life. Master's thesis, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /169652.