Dataset Information

A novel algorithm for parameter estimation of Hidden Markov Model inspired by Ant Colony Optimization.

ABSTRACT: HMM is a powerful method to model data in various fields. Estimation of Hidden Markov Model parameters is an NP-Hard problem. We propose a heuristic algorithm called "AntMarkov" to improve the efficiency of estimating HMM parameters. We compared our method with four algorithms. The comparison was conducted on 5 different simulated datasets with different features. For further evaluation, we analyzed the performance of algorithms on the prediction of protein secondary structures problem. The results demonstrate that our algorithm obtains better results with respect to the results of the other algorithms in terms of time efficiency and the amount of similarity of estimated parameters to the original parameters and log-likelihood. The source code of our algorithm is available in https://github.com/emdadi/HMMPE.

SUBMITTER: Emdadi A

PROVIDER: S-EPMC6422281 | biostudies-literature | 2019 Mar

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

A novel algorithm for parameter estimation of Hidden Markov Model inspired by Ant Colony Optimization.

Emdadi Akram A Ahmadi Moughari Fatemeh F Yassaee Meybodi Fatemeh F Eslahchi Changiz C

Heliyon 20190308 3

HMM is a powerful method to model data in various fields. Estimation of Hidden Markov Model parameters is an NP-Hard problem. We propose a heuristic algorithm called "AntMarkov" to improve the efficiency of estimating HMM parameters. We compared our method with four algorithms. The comparison was conducted on 5 different simulated datasets with different features. For further evaluation, we analyzed the performance of algorithms on the prediction of protein secondary structures problem. The resu ...[more]

PMID: 30923763

Similar Datasets

Project description:BACKGROUND:During procedures for conducting multiple sequence alignment, that is so essential to use the substitution score of pairwise alignment. To compute adaptive scores for alignment, researchers usually use Hidden Markov Model or probabilistic consistency methods such as partition function. Recent studies show that optimizing the parameters for hidden Markov model, as well as integrating hidden Markov model with partition function can raise the accuracy of alignment. The combination of partition function and optimized HMM, which could further improve the alignment's accuracy, however, was ignored by these researches. RESULTS:A novel algorithm for MSA called ProbPFP is presented in this paper. It intergrate optimized HMM by particle swarm with partition function. The algorithm of PSO was applied to optimize HMM's parameters. After that, the posterior probability obtained by the HMM was combined with the one obtained by partition function, and thus to calculate an integrated substitution score for alignment. In order to evaluate the effectiveness of ProbPFP, we compared it with 13 outstanding or classic MSA methods. The results demonstrate that the alignments obtained by ProbPFP got the maximum mean TC scores and mean SP scores on these two benchmark datasets: SABmark and OXBench, and it got the second highest mean TC scores and mean SP scores on the benchmark dataset BAliBASE. ProbPFP is also compared with 4 other outstanding methods, by reconstructing the phylogenetic trees for six protein families extracted from the database TreeFam, based on the alignments obtained by these 5 methods. The result indicates that the reference trees are closer to the phylogenetic trees reconstructed from the alignments obtained by ProbPFP than the other methods. CONCLUSIONS:We propose a new multiple sequence alignment method combining optimized HMM and partition function in this paper. The performance validates this method could make a great improvement of the alignment's accuracy.

Dataset Information

A novel algorithm for parameter estimation of Hidden Markov Model inspired by Ant Colony Optimization.

Publications

A novel algorithm for parameter estimation of Hidden Markov Model inspired by Ant Colony Optimization.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets