.png){kind=icon}
.png){kind=icon}
Return
Optimal solutions for the balanced minimum evolution problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2011.02.020.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Phylogenies are trees representing the evolutionary relationships of a set of species (called taxa). Phylogenies find application in several scientific areas ranging from medical research to drug discovery, epidemiology, systematics and population dynamics. In these applications the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the species analyzed. On the contrary, the information about the phylogeny itself is generally missing and must be determined by solving an optimization problem, called the phylogeny estimation problem (PEP), whose versions depend on the criterion used to select a phylogeny among plausible alternatives. In this paper, we investigate one of the most significant versions of the PEP, called the balanced minimum evolution problem. We propose an exact algorithm based on the enumeration of non-isomorphic trees and the subsequent solution of quadratic assignment problems. Furthermore, by exploiting the underlying parallelism of the algorithm, we present a parallel version of the algorithm which shows a linear speed-up with respect to the sequential version. Extensive computational results prove the effectiveness of the proposed algorithms. (C) 2011 Elsevier Ltd. All rights reserved.
Keywords:
Combinatorial optimization
Quadratic assignment
Computational biology
Balanced minimum evolution
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W