A novel two-level particle swarm optimization approach to train the transformational grammar based hidden Markov models for performing structural alignment of pseudoknotted RNA

A two-level particle swarm optimization (TL-PSO) algorithm is proposed for training stochastic context-sensitive hidden Markov model (cs-HMM), that addresses a thrust area of bioinformatics i.e. structural alignment of pseudoknotted non-coding RNAs (ncRNAs). Due to the well-conserved sequences and corresponding secondary structures of ncRNAs, the structural information becomes imperative for performing their alignments. Proposed approach is unique in the sense: it is the first idea so far which works on optimization of the model length; also it is the first swarm intelligence technique that is proposed for training csHMM. The two-level strategy with training and cross training sets helps in increasing the diversity of the particles so as to avoid trapping in local optima, yields more accurate estimation parameters, preserves the structure of the model and provides the best compression from the model. TL-PSO yields a trained stochastic model with position-dependent probabilities that achieves high prediction ratios than the compared non-stochastic scoring matrix based csHMM approaches. TL-PSO is also tested solely for sequence alignment of proteins, by training the conventional HMMs. TLPSO-HMM produces an effective framework for sequence alignment in terms of alignment quality and prediction accuracy than the competitive state-of-the-art and family of PSO based algorithms. Conjointly, TLPSO-csHMM finds higher prediction measures than competitive RNA structural alignment techniques for pseudoknotted and non-pseudoknotted RNA structures of diverse complexities.