论文部分内容阅读
生物信息学是一门内涵非常丰富的交叉学科,该学科的核心研究内容是使用计算机科学与技术对生物学研究的实验数据管理、统计、分析并预测,其作用已经渗透到现代生物学研究的各个主要领域和阶段。生物信息学是当前计算机科学研究中的一个热点领域。由于研究对象的背景不同,生物信息学与传统的计算机科学具有相当不同的研究特点和方法。在这个领域不断有开放性问题涌现,同时已有问题也仍然需要新的方法与技术以适应不同的应用情况。
本文深入讨论了在生物信息学研究中的两个热点问题:基因表达数据聚类分析和结构数据库搜索。我们汇总了在这两个问题上已有的工作,对其中有价值的思想,方法和技术做了总结与评估,在此基础上,提出了用于新型基因.样本.时间微阵列基因表达数据的聚类算法gTRICLUSTER和用于化学化合物分子结构数据库的子结构搜索算法GString。
与传统的聚类算法不同,gTRCLUSTER用于从新型的GST微阵列数据中挖掘一致性三维聚类簇。与已有的方法相比,gTRICLUSTER突破了强加的限制,使用了更为通用的三维聚类模型。因此,gTRICLUSTER能够找出有可能被已有方法忽略但却具有生物学重要性的一致性基因聚类簇。在真实数据库上进行的实验验证了该算法的有效性,同时显示gTRICLUSTER具有良好的噪音鲁棒性。合理地运用gTRICLUSTER可以充分利用新型微阵列数据的优势,给用户提供有用的信息。
GString是针对化学化合物分子结构数据库进行子图搜索的算法。我们从领域知识得到启发,将语义信息记录在用于表示结构的字符串中,使用合适的方法对这些字符串构建索引以支持有意义的子结构搜索操作。对于给定的查询,我们使用这些索引过滤图数据库,得到较小的候选集,减少需要进行的高时间复杂度的子图同构匹配。GString也能很方便地支持相似子图搜索问题。在真实数据集上的实验表明,与已有的方法相比,GString在索引大小,索引构建时间,索引过滤效率和准确率等主要性能指标上取得较好的平衡。在上述工作的基础上,我们开发了一个原型系统。