Dataset Information

On simulated annealing phase transitions in phylogeny reconstruction.

ABSTRACT: Phylogeny reconstruction with global criteria is NP-complete or NP-hard, hence in general requires a heuristic search. We investigate the powerful, physically inspired, general-purpose heuristic simulated annealing, applied to phylogeny reconstruction. Simulated annealing mimics the physical process of annealing, where a liquid is gently cooled to form a crystal. During the search, periods of elevated specific heat occur, analogous to physical phase transitions. These simulated annealing phase transitions play a crucial role in the outcome of the search. Nevertheless, they have received comparably little attention, for phylogeny or other optimisation problems. We analyse simulated annealing phase transitions during searches for the optimal phylogenetic tree for 34 real-world multiple alignments. In the same way in which melting temperatures differ between materials, we observe distinct specific heat profiles for each input file. We propose this reflects differences in the search landscape and can serve as a measure for problem difficulty and for suitability of the algorithm's parameters. We discuss application in algorithmic optimisation and as a diagnostic to assess parameterisation before computationally costly, large phylogeny reconstructions are launched. Whilst the focus here lies on phylogeny reconstruction under maximum parsimony, it is plausible that our results are more widely applicable to optimisation procedures in science and industry.

SUBMITTER: Strobl MAR

PROVIDER: S-EPMC4912009 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Similar Datasets

Project description:Fast Fourier transform (FFT)-based protein ligand docking together with parallel simulated annealing for both rigid and flexible receptor docking are implemented on graphical processing unit (GPU) accelerated platforms to significantly enhance the throughput of the CDOCKER and flexible CDOCKER - the docking algorithms in the CHARMM program for biomolecule modeling. The FFT-based approach for docking, first applied in protein-protein docking to efficiently search for the binding position and orientation of proteins, is adapted here to search ligand translational and rotational spaces given a ligand conformation in protein-ligand docking. Running on GPUs, our implementation of FFT docking in CDOCKER achieves a 15 000 fold speedup in the ligand translational and rotational space search in protein-ligand docking problems. With this significant speedup it becomes practical to exhaustively search ligand translational and rotational space when docking a rigid ligand into a protein receptor. We demonstrate in this paper that this provides an efficient way to calculate an upper bound for docking accuracy in the assessment of scoring functions for protein-ligand docking, which can be useful for improving scoring functions. The parallel molecular dynamics (MD) simulated annealing, also running on GPUs, aims to accelerate the search algorithm in CDOCKER by running MD simulated annealing in parallel on GPUs. When utilized as part of the general CDOCKER docking protocol, acceleration in excess of 20 times is achieved. With this acceleration, we demonstrate that the performance of CDOCKER for redocking is significantly improved compared with three other popular protein-ligand docking programs on two widely used protein ligand complex data sets: the Astex diverse set and the SB2012 test set. The flexible CDOCKER is similarly improved by the parallel MD simulated annealing on GPUs. Based on the results presented here, we suggest that the accelerated CDOCKER platform provides a highly competitive docking engine for both rigid-receptor and flexible-receptor docking studies and will further facilitate continued improvement in the physics-based scoring function employed in CDOCKER docking studies.

Project description:A comprehensive understanding of the linear/nonlinear dynamic behavior of wireless microresonators is essential for micro-electromechanical systems (MEMS) design optimization. This study investigates the dynamic behaviour of a magnetoelectric (ME) microresonator, using a finite element method (FEM) and machine learning algorithm. First, the linear/nonlinear behaviour of a fabricated thin-film ME microactuator is assessed in both the time domain and frequency spectrum. Next, a data driven system identification (DDSI) procedure and simulated annealing (SA) method are implemented to reconstruct differential equations from measured datasets. The Duffing equation is employed to replicate the dynamic behavior of the ME microactuator. The Duffing coefficients such as mass, stiffness, damping, force amplitude, and excitation frequency are considered as input parameters. Meanwhile, the microactuator displacement is taken as the output parameter, which is measured experimentally via a laser Doppler vibrometer (LDV) device. To determine the optimal range and step size for input parameters, the sensitivity analysis is conducted using Latin hypercube sampling (LHS). The peak index matching (PIM) and correlation coefficient (CC) are considered assessment criteria for the objective function. The data-driven developed models are subsequently employed to reconstruct/predict mode shapes and the vibration amplitude over the time domain. The effect of driving signal nonlinearity and total harmonic distortion (THD) is explored experimentally under resonance and sub-resonance conditions. The vibration measurements reveal that as excitation levels increase, hysteresis variations become more noticeable, which may result in a higher prediction error in the Duffing array model. The verification test indicates that the first bending mode reconstructs reasonably with a prediction accuracy of about 92 percent. This proof-of-concept study demonstrates that the simulated annealing approach is a promising tool for modeling the dynamic behavior of MEMS systems, making it a strong candidate for real-world applications.

Dataset Information

On simulated annealing phase transitions in phylogeny reconstruction.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets