Chinese Journal of Computers   Full Text
Title	A Discrete Hopfield Neural Network Based MIS Finding Algorithm for Stems Selecting and Its Application in RNA Secondary Structure Prediction
Authors	LIU Qi1) ZHANG Yin2) YE Xiu-Zi2) YU Rong-Dong1)
Address	1)(James D.Watson Institute of Genomic Sciences, Zhejiang University, Hangzhou 310008) 2)(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027)
Year	2008
Issue	No.1(51—58)
Abstract &   Background	Abstract Based on the definitions of Discrete Hopfield Neural Network (DHNN) and Maximal Independent Set (MIS) in Graph theory, a heuristic algorithm is presented to select stems in RNA structure as well as its application in RNA secondary structure prediction. The stems are mapped into an adjacent graph and the thermodynamic motion equation is defined to control the iterations of the network to find the optimal structure. Running time of this algorithm is compared with the Maximal Base Pair algorithm and Minimal Energy Algorithm. Also specific experiments are implemented to test the accuracy of the algorithm in stem and base pair levels. The results have shown that the algorithm is efficient in terms of its running time and accuracy. The time complexity of the algorithm is max｛O(n2),O(N2)｝ and the space complexity approximates to O(N2), n is the sequence length of RNA and N is stem segments number of the RNA sequence. keywords RNA; secondary structure; Maximal Independent Set(MIS); discrete Hopfield neural network; stem background Ribonucleic acid (RNA) is an important class of molecules which performs a wide range of biological and chemical functions. Traditionally, most RNA molecules were regarded as involving in the process of translation, including transfer RNA (tRNA) and ribosomal RNA (rRNA). Since the late 1990s, it has been widely acknowledged that there substantially exists other types of RNA molecules (such as small non-coding RNA) presented in organisms ranging from bacteria to mammals, which affect a large variety of processes including drugs targeting, riboswitches, plasmid replication, phage development, bacterial virulence, RNA modification and others. RNA has recently become the center of much attention because of its diversity functions, leading to a substantially increased interest in obtaining their structural information. The problem of RNA secondary structure prediction has been an interesting and challenging one for several decades, due to its importance to determination of the RNA tertiary structures and RNA functions as well as the difficulty in solving the problem. Numerous prediction methods have been developed, which include the thermodynamic energy minimization method, the phylogeny-based comparison method and the stochastic context-free grammar method. However, most of these methods are not suitable for the prediction of long RNA sequences and large-scale data analysis due to their high computational consuming. In this paper, the authors try to address this issue from a graph perspective and utilize Discrete Hopfield Neural Network (DHNN) to improve the processing speed. The results have shown that the algorithm is efficient in terms of its running time and prediction accuracy. This paper is a primary summarize of their early stage researches of parallelized RNA secondary structure prediction. The ultimate goal is to utilize parallelized clustering system to perform RNA secondary structure prediction, which could dramatically improve the prediction speed and make the more accurate prediction feasible.