用并行蚁群系统解决带假结RNA二级结构预测
|
摘要
RNA是生物遗传信息的中间载体,在基因编码、解码、调控和表达等方面具有重要作用.RNA二级结构预测是理解RNA生化功能的主要途径.假结是最广泛的RNA结构单元.带假结的RNA二级结构预测难度大,已被证明是一个NP完全问题,至今未找到该问题有效的多项式算法.本文将带假结RNA二级结构预测建模为一个多目标优化问题,在Prob Knot方法的基础上,设计两种基于碱基配对概率的改进方案,并采用最大最小蚁群方法优化原本的贪婪法.此外,引入并行的机制和共享信息素矩阵的方式,提出一种并行的带假结RNA二级结构预测方法.选取常用的RNA STRAND数据集,与常见的带假结RNA二级结构预测方法作比较.实验结果表明,本文的方法可以有效地提高带假结RNA二级结构预测的精度.
RNA is the carrier of genetic information.It plays a key role in gene encoding,decoding,regulation,expression and other aspects.RNA second structure prediction is the main way to know the biochemical functions.Pseudoknots are the most extensive RNA structure units.RNA secondary structure prediction with pseudoknots is really hard work which has been proved an NP-complete problem.A polynomial algorithm for the problem has not yet to be found.This paper models RNA secondary structure prediction with pseudoknots as a multi-objective optimization problem.Based on the ProbKnot method and RNA base-pair probability matrix,we propose two improving methods.Furthermore,we apply max-min ant system to RNA structure prediction in order to improve the greedy algorithm in ProbKnot.Besides,this paper presents a parallel approach to predict RNA second structure with pseudoknots by introducing parallelism and sharing one pheromone matrix.This approach is compared with several normal RNA secondary structure prediction methods on RNA STRAND dataset.The experimental results indicate that the parallel method is able to improve the accuracy of RNA secondary structure prediction with pseudoknots.
RNA is the carrier of genetic information.It plays a key role in gene encoding,decoding,regulation,expression and other aspects.RNA second structure prediction is the main way to know the biochemical functions.Pseudoknots are the most extensive RNA structure units.RNA secondary structure prediction with pseudoknots is really hard work which has been proved an NP-complete problem.A polynomial algorithm for the problem has not yet to be found.This paper models RNA secondary structure prediction with pseudoknots as a multi-objective optimization problem.Based on the ProbKnot method and RNA base-pair probability matrix,we propose two improving methods.Furthermore,we apply max-min ant system to RNA structure prediction in order to improve the greedy algorithm in ProbKnot.Besides,this paper presents a parallel approach to predict RNA second structure with pseudoknots by introducing parallelism and sharing one pheromone matrix.This approach is compared with several normal RNA secondary structure prediction methods on RNA STRAND dataset.The experimental results indicate that the parallel method is able to improve the accuracy of RNA secondary structure prediction with pseudoknots.
引文
[1]Mathews D H,Turner D H.Prediction of RNA secondary structure by free energy minimization[J].Current Opinion in Structural Biology,2006,16(3):270-278.
[2]Ruan J,Stormo G D,Zhang W.An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots[J].Bioinformatics,2004,20(1):58-66.
[3]Ramos S B V,Laederach A.Molecular biology:a second layer of information in RNA[J].Nature,2014,505(7485):621-622.
[4]Mathews D H,Turner D H,Zuker M.RNA secondary structure prediction[J].Current Protocols in Nucleic Acid Chemistry,2007,11(2):1-17.
[5]Zuker M,Sankoff D.RNA secondary structures and their prediction[J].Bulletin of Mathematical Biology,1984,46(4):591-621.
[6]LyngsR B,Pedersen C N S.RNA pseudoknot prediction in energy-based models[J].Journal of Computational Biology,2000,7(3-4):409-427.
[7]Stützle T,Hoos H H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.
[8]Lv Qiang,Gao Yan-ming,Qian Pei-de.Sharing one pheromone matrix:a newapproach to parallel ACO[J].Acta Automatica Sinica,2007,33(4):418-421.
[9]Zhang Hao-wen,Yang Yu-cheng,Lu Zhi.From sequence to structure:RNA secondary structure prediction methods and the applications[J].Chinese Bulletin of Life Sciences,2014,26(3):219-227.
[10]Gruber A R,Lorenz R,Bernhart S H,et al.The vienna RNA websuite[J].Nucleic Acids Research,2008,36(Sup.2):70-74.
[11]Zou Quan,Guo Mao-zu,Zhang Tao-tao.A reviewof RNA secondary structure prediction algorithms[J].Acta Electronica Sinica,2008,36(2):331-337.
[12]Harmanci A O,Sharma G,Mathews D H.Turbo Fold:iterative probabilistic estimation of secondary structures for multiple RNA sequences[J].BM C Bioinformatics,2011,12(1):1-22.
[13]Liu Zhen-dong.Studies on algorithms for RNA structure prediction including pseudoknots[D].Shandong University,2014.
[14]Bellaousov S,Mathews D H.Prob Knot:fast prediction of RNA secondary structure including pseudoknots[J].Ribonucleic Acid,2010,16(10):1870-1880.
[15]Lu Zhi Jhon,Gloor J W,Mathews D H.Improved RNA secondary structure prediction by maximizing expected pair accuracy[J].Ribonucleic Acid,2009,15(10):1805-1813.
[16]Wu Yang,Shi Bin-bin,Ding Xin-qiang,et al.Improved prediction of RNA secondary structure by integrating the free energy model with restraints derived from experimental probing data[J].Nucleic Acids Research,2015,43(15):7247-7259.
[17]Ant Colony Optimization and Swarm Intelligence:6th International Conference,ANTS 2008,Brussels,Belgium,September 22-24,2008,Proceedings[M].Springer,2008.
[18]Lv Qiang,Wu Hong-jie,Wu Jin-zhen,et al.A parallel ant colonies approach to de novo prediction of protein backbone in CASP8/9[J].Science China Information Sciences,2013,56(10):1-13.
[19]Quan Li-jun,Lv Qiang,Li Hai-ou,et al.Improved packing of protein side chains with parallel ant colonies[J].BM C Bioinformatics,2014,15(Sup.12):1-12.
[20]Adams J C,Brown R,Shoop E.Teaching parallel computing concepts with Open M P[C].Proceedings of the 47th ACM Technical Symposium on Computing Science Education(SIGCSE 2016).ACM,2016:712-713.
[21]Andronescu M,Bereg V,Hoos H H,et al.RNA STRAND:the RNA secondary structure and statistical analysis database[J].BM C Bioinformatics,2008,9(1):340-349.
[22]Gardner P P,Giegerich R.A comprehensive comparison of comparative RNA structure prediction approaches[J].BM C Bioinformatics,2004,5(1):140-157.
[23]Baldi P,Brunak S,Chauvin Y,et al.Assessing the accuracy of prediction algorithms for classification:an overview[J].Bioinformatics,2000,16(5):412-424.
[24]Deigan K E,Li T W,Mathews D H,et al.Accurate SHAPE-directed RNA structure determination[J].Proceedings of the National Academy of Sciences,2009,106(1):97-102.
[25]DBellaousov S,Reuter J S,Seetin M G,et al.RNAstructure:Web servers for RNA secondary structure prediction and analysis[J].Nucleic Acids Research,2013,41(4):471-474.
[8]吕强,高彦明,钱培德.共享信息素矩阵:一种新的并行ACO方法[J].自动化学报,2007,33(4):418-421.
[11]邹权,郭茂祖,张涛涛.RNA二级结构预测方法综述[J].电子学报,2008,36(2):331-337.
[13]刘振栋.包含假结的RNA结构预测算法研究[D].济南:山东大学,2014.
[2]Ruan J,Stormo G D,Zhang W.An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots[J].Bioinformatics,2004,20(1):58-66.
[3]Ramos S B V,Laederach A.Molecular biology:a second layer of information in RNA[J].Nature,2014,505(7485):621-622.
[4]Mathews D H,Turner D H,Zuker M.RNA secondary structure prediction[J].Current Protocols in Nucleic Acid Chemistry,2007,11(2):1-17.
[5]Zuker M,Sankoff D.RNA secondary structures and their prediction[J].Bulletin of Mathematical Biology,1984,46(4):591-621.
[6]LyngsR B,Pedersen C N S.RNA pseudoknot prediction in energy-based models[J].Journal of Computational Biology,2000,7(3-4):409-427.
[7]Stützle T,Hoos H H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.
[8]Lv Qiang,Gao Yan-ming,Qian Pei-de.Sharing one pheromone matrix:a newapproach to parallel ACO[J].Acta Automatica Sinica,2007,33(4):418-421.
[9]Zhang Hao-wen,Yang Yu-cheng,Lu Zhi.From sequence to structure:RNA secondary structure prediction methods and the applications[J].Chinese Bulletin of Life Sciences,2014,26(3):219-227.
[10]Gruber A R,Lorenz R,Bernhart S H,et al.The vienna RNA websuite[J].Nucleic Acids Research,2008,36(Sup.2):70-74.
[11]Zou Quan,Guo Mao-zu,Zhang Tao-tao.A reviewof RNA secondary structure prediction algorithms[J].Acta Electronica Sinica,2008,36(2):331-337.
[12]Harmanci A O,Sharma G,Mathews D H.Turbo Fold:iterative probabilistic estimation of secondary structures for multiple RNA sequences[J].BM C Bioinformatics,2011,12(1):1-22.
[13]Liu Zhen-dong.Studies on algorithms for RNA structure prediction including pseudoknots[D].Shandong University,2014.
[14]Bellaousov S,Mathews D H.Prob Knot:fast prediction of RNA secondary structure including pseudoknots[J].Ribonucleic Acid,2010,16(10):1870-1880.
[15]Lu Zhi Jhon,Gloor J W,Mathews D H.Improved RNA secondary structure prediction by maximizing expected pair accuracy[J].Ribonucleic Acid,2009,15(10):1805-1813.
[16]Wu Yang,Shi Bin-bin,Ding Xin-qiang,et al.Improved prediction of RNA secondary structure by integrating the free energy model with restraints derived from experimental probing data[J].Nucleic Acids Research,2015,43(15):7247-7259.
[17]Ant Colony Optimization and Swarm Intelligence:6th International Conference,ANTS 2008,Brussels,Belgium,September 22-24,2008,Proceedings[M].Springer,2008.
[18]Lv Qiang,Wu Hong-jie,Wu Jin-zhen,et al.A parallel ant colonies approach to de novo prediction of protein backbone in CASP8/9[J].Science China Information Sciences,2013,56(10):1-13.
[19]Quan Li-jun,Lv Qiang,Li Hai-ou,et al.Improved packing of protein side chains with parallel ant colonies[J].BM C Bioinformatics,2014,15(Sup.12):1-12.
[20]Adams J C,Brown R,Shoop E.Teaching parallel computing concepts with Open M P[C].Proceedings of the 47th ACM Technical Symposium on Computing Science Education(SIGCSE 2016).ACM,2016:712-713.
[21]Andronescu M,Bereg V,Hoos H H,et al.RNA STRAND:the RNA secondary structure and statistical analysis database[J].BM C Bioinformatics,2008,9(1):340-349.
[22]Gardner P P,Giegerich R.A comprehensive comparison of comparative RNA structure prediction approaches[J].BM C Bioinformatics,2004,5(1):140-157.
[23]Baldi P,Brunak S,Chauvin Y,et al.Assessing the accuracy of prediction algorithms for classification:an overview[J].Bioinformatics,2000,16(5):412-424.
[24]Deigan K E,Li T W,Mathews D H,et al.Accurate SHAPE-directed RNA structure determination[J].Proceedings of the National Academy of Sciences,2009,106(1):97-102.
[25]DBellaousov S,Reuter J S,Seetin M G,et al.RNAstructure:Web servers for RNA secondary structure prediction and analysis[J].Nucleic Acids Research,2013,41(4):471-474.
[8]吕强,高彦明,钱培德.共享信息素矩阵:一种新的并行ACO方法[J].自动化学报,2007,33(4):418-421.
[11]邹权,郭茂祖,张涛涛.RNA二级结构预测方法综述[J].电子学报,2008,36(2):331-337.
[13]刘振栋.包含假结的RNA结构预测算法研究[D].济南:山东大学,2014.