Evolutionary computation and applications in bioinformatics

本研究计划的目标是：1)在本实验室已有算法的基础上，针对生物信息学中的问题开发改进的组合算法，特别是对生物分子结构的预测。2)扩展RNA二级结构可视化工具jViz.Rna。本实验室开发的基于进化计算的算法Rna Predict已被证明能够以非常高的准确率(高达90%)预测某些已知的RNA二级结构，并对某些中短序列具有比目前从头预测RNA二级结构的基准mFold更高的预测精度。特别是，Rna Predict不像mold那样容易预测假阳性。Rnapredict使用了许多高级运算符和表示法。我计划进一步评估、改进和扩展Rna Predict。我已经开发了一种RNA二级结构可视化工具，它与现有工具相比具有许多优点，包括：广泛支持输入和输出格式，能够产生高质量的图形以供复制，交互输出以供最终用户进一步操作，能够在经典结构图中显示伪结点，以及能够覆盖两种不同的结构以进行比较。JViz.RNA还对两种结构进行定量和定性比较。定量比较目前考虑了敏感度、特异度和F测量。我计划扩展jViz.RNA，使用对偶图对基于公共子结构的结构进行比较。

The objectives of this research program are:1) To develop improved combinatorial algorithms for problems in Bioinformatics, particularly for structure prediction of biomolecules, building on the algorithms that have been developed in my lab so far2) To extend jViz.Rna, a visualization tool for RNA secondary structureThe algorithm RnaPredict, developed in my lab and based on evolutionary computation, has been demonstrated to predict certain known RNA secondary structures with very high accuracy (up to 90%) and to have a higher prediction accuracy on certain short and medium length sequences than mfold, the current benchmark for ab initio RNA secondary structure prediction. Particularly, RnaPredict is not as prone to predicting false positives as mfold is. Rnapredict uses a number of advanced operators and representations. I plan to further evaluate, improve, and extend RnaPredict. I have developed a visualization tool for RNA secondary structure which has a number of benefits over existing tools, including: wide support of input and output formats, ability to produce high quality graphics for reproduction, interactive output for further manipulation by the end user, ability to display pseudoknots in a classical structure plot, and the ability to overlay two different structures for comparison. jViz.Rna also produces quantitative and qualitative comparisons between two structures. The quantitative comparison is currently taking into account sensitivity, specificity, and F-measure. I plan to extend jViz.RNA to incorporate a comparison of structures based on common substructures using dual graphs.