生物信息的计算模型与算法研究

生物信息的计算模型与算法研究

ID:41026265

大小:4.06 MB

页数:120页

时间:2019-08-14

生物信息的计算模型与算法研究_第1页
生物信息的计算模型与算法研究_第2页
生物信息的计算模型与算法研究_第3页
生物信息的计算模型与算法研究_第4页
生物信息的计算模型与算法研究_第5页
资源描述:

《生物信息的计算模型与算法研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、中国科学技术大学博士学位论文生物信息的计算模型与算法研究姓名:鄢超申请学位级别:博士专业:计算机软件与理论指导教师:陈国良20040501中潮科学接寒大学搭士学位论文接要摘要生物信息学楚计算分子生物学与计算机科学之间的麓叉学科。近年来,随着计算技术的交飞糕进,生物技术正给整个人类带来前所朱有的巨大变化。本文围绕擞物信息的计算模型与算法开展研究,主要内容、贾敞和创新包括(1)基因表迭式数据的计算基因表迭式数据是跌绔梦嘻教据抽象得翻的。由于表逡式数据忽略了原始数据的一些细节,因衙能够适应一癜诸如聚类和丹类分析的“宏观”研究,而

2、这两类冀耀燕数据挖巍中的经典溺越,在生耪髂惑簇域宅有重簧酶应弱徐{轰。袁这式数据能够排成矩阵'If;式,适用于数据挖掘。本炙的主要工作是:①讨论了聚类和异类分辑砖概念、黎本蒡法争劳瓣点,蟹对巍缝空阏中薯类分辑戆霹难,提虫了一个敲于遗传机制的新的用于生物表达式数据异类分析的薄法,为解决穷举法寻找子蜜惩砖带来的爆沣{十算量鞠摄蠹提供了有效手段;②该雾法改进了基5-距离方法来昂找异类数据,减少了对邻近数据的搜索,并用欧氏几何学、积分筝数学工具对设改进进行了域论分析;③农酵母茵、人类和淋巴瘴数据上进行实验,证明了该嚣法的实用性和改

3、进的效率。由于该算法能对产生的予空间解给出一定的生物学上的解释,即频繁出现的维表明其对应的基因段具有多样性,因此譬找异类数据过程中找翻砖予空间本身嚣有更重要酶价值。鼠并类分析的角度看,该方法具有一定的普适性,能够被用于对其它高维数据的异类分析。(2>生赞镑葬摸壁戆辨霓斑物计算往被涉及大计算赞,因此并行化的设计是必不可少的。农研究生物蓐刭骨箕中豹双序载比对问题靖,褥题本身酶亭嚣楚理耱控使铎芳野建理较蔗窭难。研究中发现由荧国公司提出的一种新的并行计算模擞一一CellMatrixTM能较中国科学技术大学博士学位论文摘要好的解决该

4、问题,其同构的二维结构便于生产和扩展,是一种典型的纳米计算模型。由于DNA序列的特性,每个核苷酸都可以由固定长度的二进制数表示,用该结构来实现双序列计算非常自然。本文的主要工作是:①研究了该模型上已有的双序列比对算法,针对其只能输出最佳罚分值的缺陷进行了改进,对动态规身矩阵进行回溯并统计各个位置插入的空格数,使得算法同时还能输出最佳比对;②以平衡分组选择网络的实现为倒,介绍了一种以晶格数目开销和晶格延迟时间两方面为基础的开销分析方法,将这种方法应用到对前述双序列比对算法的分l析,验证了该算法的有效性。另外,针对并行算法的通

5、信开销问题,本文还对另一种新的计算模型LARPBS进行了研究。由于该模型具有·}夹速重构、通信操作时间短等优点,使得在LARPBS上设计算法可以大大减小时间开销。本文中后续部分将介绍在LARPBS上的多序列比对算法。(3)生物序列的计算生物序列信息是最基本的生物信息,包括DNA序列和蛋白质序列,本文的研究重点是前者。我们研究了多序列比对问题的算法,提出了两个并行近似算法。首先,在经典的SIMD.CREW模型上,给出了一个使用k2m个处理器,时间复杂度为O(m+logk)t约并行近似算法(其中m是序列长度,k是序列个数),理

6、论上达到了线性加速。其次,还结合新模型LARPBS的特点,首次给出了一个在LARPBS模型上的求解多序列比对问题的并行近似算法,在理论上也达到缌l生加速,且比前一个算法在时间开销上大为减少。关键词:生物信息学,基因表达式数据、数据挖掘、聚类、异类分析,并行算法,并行计算模型,CellMatrixTM,生物序列,序列比对。2中国科学技术大学博士学位论文摘要AbstractBioinformaticsistheinterdisciplineofcomputationalmolecularbiologyandcomputersc

7、ience.Withtherapiddevelopmentofcomputingtechniques,biologicaltechnologiesarereshapingthehumansociety.Thispaperstudiesthecomputingmodelsandalgorithmsforbioinformatics.Themaincontent,contributionandinnovationinthepaperaredescribedbelow.(1)Thestudyofcomputationsongen

8、eexpressiondataGeneexpressiondataareacquiredbyrefiningsequences.Suchdataneglectmanydetailsandfitsome“macroscopical”research,suchasclusteringandoutlieran

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。