• /  120
  • 下载费用: 20.00积分  

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

'生物信息的计算模型与算法研究'
中国科学技术大学 博士学位论文 生物信息的计算模型与算法研究 姓名:鄢超 申请学位级别:博士 专业:计算机软件与理论 指导教师:陈国良 20040501 中潮科学接寒大学搭士学位论文 接要 摘要 生物信息学楚计算分子生物学与计算机科学之间的麓叉学科。近年来,随着 计算技术的交飞糕进,生物技术正给整个人类带来前所朱有的巨大变化。本文围 绕擞物信息的计算模型与算法开展研究,主要内容、贾敞和创新包括 ( 1 ) 基因表迭式数据的计算 基因表迭式数据是跌绔梦嘻教据抽象得翻的。由于表逡式数据忽略了原始数据 的一些细节,因衙能够适应一癜诸如聚类和丹类分析的“宏观”研究,而这两类 冀耀燕数据挖巍中的经典溺越,在生耪髂惑簇域宅有重簧酶应弱徐{ 轰。袁这式数 据能够排成矩阵' I f ;式,适用于数据挖掘。本炙的主要工作是:①讨论了聚类和异 类分辑砖概念、黎本蒡法争劳瓣点,蟹对巍缝空阏中薯类分辑戆霹难,提虫了一 个敲于遗传机制的新的用于生物表达式数据异类分析的薄法,为解决穷举法寻找 子蜜惩砖带来的爆沣{ 十算量鞠摄蠹提供了有效手段;②该雾法改进了基5 - 距离方法 来昂找异类数据,减少了对邻近数据的搜索,并用欧氏几何学、积分筝数学工具 对设改进进行了域论分析;③农酵母茵、人类和淋巴瘴数据上进行实验,证明了 该嚣法的实用性和改进的效率。由于该算法能对产生的予空间解给出一定的生物 学上的解释,即频繁出现的维表明其对应的基因段具有多样性,因此譬找异类数 据过程中找翻砖予空间本身嚣有更重要酶价值。鼠并类分析的角度看,该方法具 有一定的普适性,能够被用于对其它高维数据的异类分析。 ( 2 生赞镑葬摸壁戆辨霓 斑物计算往被涉及大计算赞,因此并行化的设计是必不可少的。农研究生物 蓐刭骨箕中豹双序载比对问题靖,褥题本身酶亭嚣楚理耱控使铎芳野建理较蔗窭 难。研究中发现由荧国公司提出的一种新的并行计算模擞一一C e l lM a t r i x T M 能较 中国科学技术大学博士学位论文摘要 好的解决该问题,其同构的二维结构便于生产和扩展,是一种典型的纳米计算模 型。由于D N A 序列的特性,每个核苷酸都可以由固定长度的二进制数表示,用 该结构来实现双序列计算非常自然。本文的主要工作是:①研究了该模型上已有 的双序列比对算法,针对其只能输出最佳罚分值的缺陷进行了改进,对动态规身 矩阵进行回溯并统计各个位置插入的空格数,使得算法同时还能输出最佳比对; ②以平衡分组选择网络的实现为倒,介绍了一种以晶格数目开销和晶格延迟时间 两方面为基础的开销分析方法,将这种方法应用到对前述双序列比对算法的分 l 析,验证了该算法的有效性。 另外,针对并行算法的通信开销问题,本文还对另一种新的计算模型 L A R P B S 进行了研究。由于该模型具有·} 夹速重构、通信操作时间短等优点,使得 在L A R P B S 上设计算法可以大大减小时间开销。本文中后续部分将介绍在 L A R P B S 上的多序列比对算法。 ( 3 ) 生物序列的计算 生物序列信息是最基本的生物信息,包括D N A 序列和蛋白质序列,本文的 研究重点是前者。我们研究了多序列比对问题的算法,提出了两个并行近似算法。 首先,在经典的S I M D .C R E W 模型上,给出了一个使用k 2 m 个处理器,时间复 杂度为O ( m + l o g k ) t 约并行近似算法( 其中m 是序列长度,k 是序列个数) ,理论上 达到了线性加速。其次,还结合新模型L A R P B S 的特点,首次给出了一个在 L A R P B S 模型上的求解多序列比对问题的并行近似算法,在理论上也达到缌l 生加 速,且比前一个算法在时间开销上大为减少。 关键词:生物信息学,基因表达式数据、数据挖掘、聚类、异类分析,并行算法, 并行计算模型,C e l lM a t r i x T M ,生物序列,序列比对。 2 中国科学技术大学博士学位论文摘要 A b s t r a c t B i o i n f o r m a t i c si st h e i n t e r d i s c i p l i n e o fc o m p u t a t i o n a lm o l e c u l a rb i o l o g ya n d c o m p u t e rs c i e n c e .W i t ht h er a p i dd e v e l o p m e n to fc o m p u t i n gt e c h n i q u e s ,b i o l o g i c a l t e c h n o l o g i e sa r er e s h a p i n gt h eh u m a ns o c i e t y .T h i sp a p e rs t u d i e st h ec o m p u t i n g m o d e l sa n da l g o r i t h m sf o rb i o i n f o r m a t i c s .T h em a i nc o n t e n t ,c o n t r i b u t i o na n d i n n o v a t i o ni nt h ep a p e ra r ed e s c r i b e db e l o w . ( 1 ) T h es t u d yo fc o m p u t a t i o n so ng e n ee x p r e s s i o nd a t a G e n ee x p r e s s i o nd a t aa r ea c q u i r e db yr e f i n i n gs e q u e n c e s .S u c hd a t an e g l e c tm a n y d e t a i l sa n df i ts o m e “m a c r o s c o p i c a l ”r e s e a r c h ,s u c ha sc l u s t e r i n ga n do u t l i e ra n a l y s i s , w h i c ha l eb a s i ci nd a t am i n i n g .E x p r e s s i o nd a t ac a nb ea r r a n g e di nm a t r i c e sf o rd h t a m i n i n g .O u rm a j o rc o n t r i b u t i o n sa r e :①D i s c u s s i n gc o n c e p t s ,a l g o r i t h m s ,s i m i l a r i t i e s a n dd i s s i m i l a r i t i e so fc l u s t e r i n ga n do u t l i e ra n a l y s i sa n db r o a c h i n gan e wa l g o r i
关 键 词:
生物 信息 计算 模型 算法 研究
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:生物信息的计算模型与算法研究
链接地址: https://www.wenku365.com/p-41026265.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开