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

Area of Science:

• Computational Biology
• Machine Learning
• Bioinformatics

Background:

• Hidden Markov Models (HMMs) are widely used for data modeling across diverse scientific fields.
• Estimating HMM parameters is computationally challenging, classified as an NP-Hard problem.
• Existing methods for HMM parameter estimation can be inefficient for complex datasets.

Purpose of the Study:

• To develop a more efficient heuristic algorithm for Hidden Markov Model parameter estimation.
• To evaluate the performance of the proposed algorithm against existing methods.
• To assess the algorithm's utility in a practical bioinformatics application.

Main Methods:

• A novel heuristic algorithm, named AntMarkov, was developed for HMM parameter estimation.
• The AntMarkov algorithm was compared with four other established algorithms.
• Performance evaluation involved simulated datasets with varying characteristics and a real-world problem: protein secondary structure prediction.

Main Results:

• AntMarkov demonstrated superior time efficiency compared to the other algorithms tested.
• The algorithm achieved higher similarity between estimated and original HMM parameters.
• AntMarkov also yielded improved log-likelihood values, indicating better model fit.

Conclusions:

• The AntMarkov algorithm offers a significant improvement in the efficiency and accuracy of Hidden Markov Model parameter estimation.
• This heuristic approach provides a valuable tool for applications requiring robust HMM parameter estimation, such as in bioinformatics.
• The source code is publicly available for further research and application.