（计算机软件与理论专业论文）生物信息的计算模型与算法研究.pdf

中潮科学接寒大学搭士学位论文 接要 摘要 生物信息学楚计算分子生物学与计算机科学之间的麓叉学科。近年来，随着 计算技术的交飞糕进，生物技术正给整个人类带来前所朱有的巨大变化。本文围 绕擞物信息的计算模型与算法开展研究，主要内容、贾敞和创新包括 ( 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 t h m f o ro u t l i e ra n a l y s i si nh i 曲- d i m e n s i o n a ls p a c ew h i c hu s e st h ee v o l u t i o n a r ym e c h a n i s m t os o l v et h ep r o b l e mo fh u g en u m b e r so fs u b s p a c e s ；w ea d o p tt h ed i s t a n c e - b a s e d m e t h o db u tm a k es o m em o d i f i c a t i o nt oi tt or e d u c et h es e a r c h i n go fn e i g h b o r i n gd a t a a n dm a k et h e o r e t i c a l a n a l y s i so ft h em o d i f i c a t i o nb ye u c l i d e a ng e o m e t r ya n d a c c u m u l u s ；e x p e r i m e n t so ny e a s t , h u m a na n dl y m p h o m ad a t ap r o v et h ee f f i c i e n c y o ft h e a l g o r i t h m a n dt h em o d i f i c a t i o n a st h e a l g o r i t h m c a ng i v e b i o l o g i c a l e x p l a n a t i o n st ot h es u b s p a c es o l u t i o n si tp r o d u c e s - ad i m e n s i o nw i t hah i g hf r e q u e n c y i ns o l u t i o n sm a yc o i t e s p o n dt oag e n ew i t hh i g hd i v e r s i t y , t h u ss u b s p a c e sf o u n di n s e a r c hf o ro u t l i e r sa l eo fm o r ei m p o r t a n c e l a s t ，t h ea l g o r i t h mc a nb eu s e df o r h i 曲- d i m e n s i o n a ld a t ao t h e rt h a ng e n ee x p r e s s i o nd a t a ( 2 ) t h es t u d yo fa r c h i t e c t u r e sf o rb i o i n f o r m a t i e s b i d i n f o r m a t i c si n v o l v e sh u g ea m o u n to fc o m p u t a t i o n si nw h i c hp a r a l l e lc o m p u t i n g i si n d i s p e n s a b l e f o rt h ep a i r w i s ea l i g n m e n t , t h ep r o b l e mi t s e l fi ss e q u e n t i a la n dh a r d t ob ep a r a l l e l i z e dt h es t u d yo ni ts h o w st h a tan e wp a m l l e lc o m p u t i n g c e l lm a t r i x r ” b r o a c h e db yau s c o m p a n y , c a ns o l v e t h e p r o b l e m i t sh o m o g e n o u s a n d t w o d i m e n s i o n a ls t r u c t u r ee n s u r e sm a n u f a c t u r i n ga n ds c a l a b i l i t y a sd n as e q u e n c e s c o n s i s to fn u c l e o t i d e st h a tc a nb er e p r e s e n t e db yb i n a r yn u m b e r so ff i x e dl e n g t h ，t h i s s t r u c t u r ei ss p o n t a n e o u s l ys u i t a b l ef o rp a i r w i s ea l i g n m e n t s ，o u rm a j o rc o n t r i b u t i o n s a r e ：s t u d y i n gac u r r e n tp a i r w i s ea l i g n m e n ta l g o r i t h mo nt h i s a r c h i t e c t u r ea n d m a k i n gr e v i s i o n st oi tb yt r a c i n gb a c kt h ed y n a m i cp r o g r a m m i n gm a t r i xs ot h a ti t c a n o u t p u ta l i g n m e n t s a sw e l la st h em a x i m u ms c o r e ；a ne x a m p l eo fs e l e c t i o n n e t w o r k si sg i v e nt oi n t r o d u c eac o m p l e x i t ya n a l y s i sm e t h o db a s e do nc e l ln u m b e r s 3 中国科学技术大学博士学位论文 摘要 a n dc e l ld e l a y s a n dm e a n w h i l et h em e t h o di su s e do nt h ea b o v e m e n t i o n e dp a i r w i s e a l i g n m e n ta l g o r i t h mt ov e i l f yi t se f f i c i e n c y w ea l s os t u d ya n o t h e rn e wm o d e ll a r p b s ，f o rt h es a k eo fl e s sc o m m u n i c a t i o n t i m ef o rp a r a l l e la l g o r i t h m s t h i sr e c o n f i g u r a b l em o d e lc a l lr e d u c ec o m m u n i c a t i o n e f f i c i e n t l yt h ef o l l o w i n gp a r tw i l li n t r o d u c eam u l t i p l ea l i g n m e n ta l g o r i t h mo ni t ( 3 ) t h es t u d yo fc o m p u t a t i o n so hb i o l o g i c a ls e q u e n c e s s e q u e n c e s ，i n c l u d i n gd n as e q u e n c e sa n dp r o t e i ns e q u e n c e s ，a r e t h em o s t f u n d a m e n t a la m o n ga l lb i o l o g i c a ld a t a o u rf o c u si so nd n as e q u e n c e s b a s e do nt h e s t u d yo fm u l t i p l es e q u e n c ea l i g n m e n t ，w eb r o a c ht w op a r a l l e la p p r o x i m a t i o n a l g o r i t h m s o n ei sb a s e do nt h ec l a s s i cs i m d - c r e wm o d e l u s i n g mp r o c e s s o r s a n dw i t ht h et i m ec o m p l e x i t yo f o ( m + l o g k ) ，w h e r em i st h el e n g t ho f s e q u e n c e sa n dk i st h en u m b e ro fs e q u e n c e s t h eo t h e ri st h ef i r s to n ef o rm u l t i p l ea l i g n m e n t so nan e w m o d e l - - l a r p b sa n di ti sf a s t e rt h a nt h ef o r m e ro n eo ns i m d - - c r e w t h eu n i q u e f e a t u r eo fl a r p b se n s u r e si t sm o r ea p p l i c a t i o n sf o rb i o i n f o r m a t i c s b o t ha r e l i n e a r - s p e e d u pa l g o r i t h m s k e yw o r d s ：b i o i n f o r m a t i e s ，g e n ee x p r e s s i o nd a t a ，d a t am i n i n g ，c l u s t e r i n g ，o u t l i e r a n a l y s i s ，p a r a l l e la l g o r i t h m ，p a r a l l e lc o m p u t i n gm o d e l ，c e l lm a t r i x t ”， b i o l o g i c a ls e q u e n c e ，s e q u e n c ea l i g n m e n t 4 孛国瓣学技拳大学鞲士学位论文 莓i 章缝论 第1 章绪论 生物信息学是i 驻年来一个新必的交叉学料。本章阐述生物信息学的概念、研 突领域移应强。在憨缝、分辑和浮述瑗毒骚究戆遴震馕况戆莛礁上，提爨本文熬 研究内容和研究愚路：列出经常发表算法研究成果的文献资源班供参考：最后给 出论文的章节安排。 1 1 生物信怠学 在浩瀚的宇宙中，有这样颗彳亍星，她的大气层中翱翔羞鸟类，她的地砸上 生长薷穗物，奔蓬羲动物，魏静瘩量遂游着鱼类。楚就是我稻的家霾麓球，也是 我们融知的宇宙中唯一存在生命的地方。作为万物之首的人类，从一出现就开始 对生命的本质万分好奇，不懈的探索着生命背后的秘密。在古代，神秘擞义者认 为生禽是由毒枣裁造豹，是圭灵魂控裁戆。到了中蹩纪，夔蕊瓣蘩学懿发鼗，开始 有人把生命看成是机械的组合；遮一对期，人们逐渐认识戮生命是物质的，是可 以认识的。十九世纪的三大发现有两个是关于舷物学的，一个是细胞的发现，另 一个是遴忧论，这使得人类对予嫩命的认识前进了一大步。这些认识过裰充分体 凌了入炎对生螽本藤不懈探索豹韩大精神。 然而，直到上馓纪中叶，人裟才真正开始接触到生命的本质。1 9 5 3 年，在 遗传学领域，沃森和克里克发现丁遗传物质脱氧核糖核酸( d n a ) 的双螺旋结 狡，掀开了瑷代生貔学熬簇章。d n a 双穗瓣每条基a 、薯、g 、c 疆释核蓊酸( 碱 基) 丰句成，其中一条的a 与另一条的t 匹配，g 与c 匹配。生命的最终艇秘就 藏在这样简洁明了的序列当中，遮令人们不由得赞叹大自然的伟大力量。在此基 础上，分子生物学开始蓬勃发展并衍生出计算分子生物学。同一时期，人类的一 璜镲大发明一一诗箨梳诞生了。诗算分子生锈擘由于其磺究领域涉及到大萤麓计 算问题，因此很自然的同计算机科学结合，产生了一门全新的学科一一生物信息 学。 一般谈为，生携痿患学裁是蠲诗算援镁城凌瓣知识秘技本来解涤分子璧兹学 中的计算问题的学科。其解决的计算问题，可以是分子生物学本来就有的计算问 题，如序列比对、蛋白质结构预测等，也可以魑计算机专家根据自身专业知识提 出的掰阀题，如生物信息的压缀鞠数据挖掘等。出此可见，生物信息学楚生物学 与计簿科学结合酌产物，二者楚赢动关系：一方两，生豹掌麴发震产生浆计算滴 砖 中国科学技术大学博士学位论文第1 瞰绪论 蹶对诗算科学掇蹬薪的研究谖溪，从丽推动冀发曩；另一方霆，计算科学骢发展 谯在不断加深人们对生物学静认识。 如今，生物信息学的研究领域已经延伸列我们生活中的备个方面。我们屹的， 肖转基因食品；我们穿的，有转基因棉；以前无法治疗的遗传瘸，现在芷褥渐被 竣毙。近年来，辩学家在该镶域取撂了令人骥籍泌残就。捌翔上藿纪寒豹蹙囊技 术，不仅震动了科学界，还i | 发了一系列伦理与法律上的大讨论。目前，科学家 m 在进行人类藏因详细图谱的绘制工作，有理由相信，该图谱完成后，必将对生 物学、医学、法学、社会学等诸多领域产生深远影响。正因为如此。很多人认为， 本避纪将是生物技术豹整纪。在这：臣全殍螽逐中，我蓬秘攀家基蒸馕参与，不霞 对人类基因图谱的绘制起着羹臻作用，取得了独立完成水稻蒸因图谱绘制j l ：作等 成就，得到了广泛好评。 生物信息学的主要研究领域是很宽的。一般来说，只要是分子生物学所需要 戆诗箕淘嚣，赘霹瑷列入其中。裁嚣蘸，臻炎鹣重焘主要怒在生稼旁到上。生耪 序列有两种，一种是我们前面提到韵d n a 序列，另一种熙鬣白质序列。瑕白质 也是一种生物大分子，它是由数目众多的氨熬酸组成的链，往往在三维空间中折 叠成复杂的缩构。已知的氨基酸有2 0 种，人所需要的是其中的1 6 种。现代生物 学表疆”j ，d n a 是蘧转穆囊静臻蒂者，d n a 上有些区域楚编鼹区，瑁王使棱营 酸( 共6 4 种) 组合表示一个氪基酸。生物体利用d n a 上的编码区，可以制造 出各种所需的蛋白质分子，从而实现各种生理机能。然而。d n a 序列是很长的， 倒姬，。个人大约蠢3 0 亿对碱繁，要完全弄清楚其会义是s 紫困难鲍。嚣越酸究 入员所骰的1 ：绺，就是一点一点的分拆比较，蟥终完全解帮其中豹奥秘。箕巾豁 许多工作，涉及到繁杂的计算，离开计算机只凭人力是无法想象的。另外，随着 生物技术的日新月异，人类获取的序列数据日蘸“泛滥”，这就要求不仅必须要 瑙计算瓤处理，嚣且要瘸计算梳采赢效处理。要提毫处理翡效率，必然离不舞计 算枕专家静辛勤劳动，包括改进算法、改进体系结构等方蕊。 1 2 生物序列上的计算 本节简要介绍生物序列上计算的背景、现状和趋势。遮类问题针对的d n a 序列和蛋白质序列，这两类序列上的问题是截然不同的。我们的研究蘑点是在 d n a 彦到上。 1 2 1 序列测定、组合与比j c 寸 d n a 彦巅与爱鑫蒺彦列褪跑较，要长褥多。萃条救d n a 彦襄透鬻瀵凝下缝 中国科学技术大学博士学位论文第1 章绪论 绕盘缩在细胞核中，由于其非常长，目前技术上还无法一次测出整条序列，因此 只能先分段测序，然后进行组合。这就好比进行。场拼图游戏，只不过面对的是 有3 0 亿对碱基的问题规模，其难度可想而知。 拼出的足够长的片段，可以作为进一步研究分析的基础。例如，需要从d n a 序列中区分编码区和非编码区，进而从编码区中找出基因。编码区是那些表示氨 基酸链的区域，直接影响的蛋白质的合成。基因是遗传物质的基本单位，是d n a 分子中特定的核苷酸序列，一个人大约有近1 0 万个基因。对于非编码区，目前 人们的认识还很有限，已经知道有些部分是起间隔作用，有些部分起到逻辑联结 作用，但仍有很多未知内容。另外，序列之间的比对是生物信息学中的最基本问 题之一，已经有了大量的相关研究 2 h 4 l 】，在筇5 章中我们会有详细介绍。其基 本问题是比较两个或两个以上生物符号序列的相似性或差异性，而蛋白质分子之 间的比对一般称为结构比对。比对有着广泛的应用。例如不久前英美学者在自 然杂志上发表论文，表明人类和老鼠的基因有9 9 都是相同的；这个比例就是 通过序列比对的方法得到的。现代医学技术中的血缘鉴定，其本质上也是序列比 对问题的应用。 1 2 2 序列压缩 考虑到序列如此之长，人们很自然的会想：能否将序列进行压缩存储呢? 研 究人员已经考虑到了这个问题，并提出了一系列的解决方案【4 2 【4 “。然而，该问 题极具挑战性由于人们对序列内部的成分和含义还所知甚少，所以现有的算法 压缩比普遍不高。该问题的探索过程，同时也是解开d n a 序列奥秘的过程。 1 2 3 单倍体计算 另一类序列上的计算问题是单倍体型的推导。我们知道，高等动物如人都是 双倍体型的：人有2 3 对染色体，每对都分别米自父母双方，是生殖细胞减数分 裂后结合的产物。现在由于实验条件的限制，我们能观察到的都是双倍体型的表 现特征；如何根据若干双倍体型的特征反推出单倍体型的特征呢? 由于单倍体型 在育种、变异研究等领域有着广泛的应用，该领域在今年逐渐成为新的热点 【4 7 】 6 8 1 。 由于序列上的研究领域广泛，涉及的生物学知识和数学工具众多，我们无法 一一详尽列举并进行研究。还有一些重要问题，如蛋白质的三维结构预测、种族 树构建、非编码区的研究等，本文的研究没有涉及到但这并不表示这些问题不 中国科学技术大学博士学位论文 第l 章绪论 重要。对于序列上的计算，本文将在第5 章中进行详细介绍，主要涉及到序列比 对、压缩、单倍体问题三方面。 1 3 生物基因表达式上的数据挖掘 1 3 1 数据挖掘 数据挖掘或知识发现是近年来计算机领域的新兴研究热点，其研究内容是从 大量的数据中抽取出潜在的、不为人知的有用信息、模式和趋势。该研究方向可 以看作是人工智能的一个分支。在现实中，面对大量的未知领域，数据挖掘可以 为我们提供一些粗略的分析和指导，辅助我们更快更好的了解该领域。很明显， 生物序列中存在许多未知信息和模式，考虑用数据挖掘的方法处理生物数据是一 件很自然的事情。比如，有的遗传疾病是多个基冈共同起作用的结果，那么面对 许多这种病人的d n a 数据，我们如何从中找出共同的特征呢? 还有些疾病的发 作有阶段性，每个阶段有特定的基因控制，如何找出这些“幕后黑手”呢? 有些 人天然就对艾滋病有免疫力，这究竟是哪里的基因不同的结果呢? 诸如此类的问 题，都可以用数据挖掘来处理。 然而在实际应用中，序列数据并不便于数据挖捌。试想，面对冗长的d n a 序列，都是四种核苷酸的重复，数据挖捌如何着手呢? 再来看看上一段中的例子 可以发现，数据挖掘应当是在基因级别而不是原始序列级别上进行。当代生物技 术的发展，提供了一一种基因表达式数据【6 9 】，正好满足数据挖捌的需要。该技术 将序列上的基因表示成实数形式，方便了计算和区分。不同序列上的相对应基因， 正是依靠数值来进行区分的。 下面我们介绍基因表达式数据上的两类主要计算问题：聚类和异类分析。 1 3 2 聚类 聚类是将输入数据按相似度分类，归于使得同一类数据之间的相似度大，不 同类数据之间的相似度小【7 。这样讲可能有些抽象，举个例子就好理解了：古 人夜观天象，将全天恒星划分为8 8 个星宿，这就是最典型的聚类问题。星宿的 划分，一般要选取那些相互较近、能组成有意义图案的恒星。这8 8 个星宿，各 自有各自的形状，这些形状就是聚类的形状。 通过对基因表达式数据聚类，我们能将数据进行归类区分。对同一类中的数 中嘲科学技术大学博士学位论文 第1 章绪论 据，可能存在某种耀厨的机制，褥归类以后馒褥| ：主屠的研究鸯了基础，准确挂也 大大撬高。对予不溺类之闻静数据，探璃它翻羽不嚣本囊氇怒缀有必要嚣。逡些 研究，都依赖于预先用聚类方法对数据进行处理。 目前已经有了许多成熟的聚类算法川【8 2 1 。在筇四章中，我们将详细介绍它 们。 1 3 3 异类分析 在数据挖援懿骚究孛，还骞穗与聚类“毒羹反”救蠢题，耀雾类分裁。雾类 分年斤的目的是找磷数据集舍中的离群数据。显然，异类分析与聚类相比，嵬侧重 的越异常的数据。异类数据背后往往隐藏着与其他数据不同的机制，因而异淡数 据的研究有重要的价值。对于生物数据而言，昴类数据可能搦示新的变异、独特 瓣痰瘸或免疫力等。 我们在现实生活中是如何送分哪些是离群数据的昵? 截喇显，一般我们总是 凭经验判断群体的特征，然后挑出不符合特征的数据。如果数据可以直观的寝示 成一个个点，则我们可以轻易的挑出那些远离冀他数据的点或是数据分布稀疏处 豹点终必一类数攒。瓣于基嚣襞达式数据，我嚣l 氇可鞋采趱类鸯羹静方法。文献 【8 3 ， 9 3 】是一些常粥的异类分析算法，在第3 章中，我们不仪要讨论各种异凝分 折算法，还要介绍我们的新算法。 1 4 本文的研究内容秘研究恿路 如上文所述，生物信息学的研究既具有蕈要的理论意义又具有广泛的应用价 毽，这正是啜；l 我翻学习秘疆突宅静攫本魂撬+ 垒是我 f j 熬兴趣瑟在。生携臻怠 正交得越来越宏大、越来越呈现昴构性( 例如，不同类型、不同级别的各类数据 以及数据库) 和越来越倾向于出现错误，这些事实向人们提出了设计更高效的算 法的挑战，同时也为我似学习和研究生物信息学盼算法提供_ 机遇。对现蠢研究 残鬃静惑结耧分孝厅裘骥；磐象我 】整续努办辑究秘簿索生镑镁域建筑诗冀瓣遂， 那么改进某些已肖的结果或者获得一些新结果仍是很有可能的。 顺序算法是撤解问题的基础，并行算法则熄加快大规模问蹶的求解速度和提 高瓣的精度的重要手段。我们将从审圣亍算法和弗露算法两方瑟鼹开研究。对予有 些阏麓，镄鲡净硼托对，盘予其潮有的线程特瞧簿法不荔予势萼亍化，繇醴我雷j 将 着重研究新的并行结构，选择合邋的计算模型设计相应的并行算法。我们将研究 如下几个问题： 中国科学技术大学博士学位论文第l 章绪论 ( 1 ) 基因表达式数据上的计算问题 由于原始的序列数据不能适应一些抽象级别上的计算问题，研究人员引入了 基因表达式数据的概念。表达式数据是对序列的抽象，它们组成的是“二级数据 库”。由于表达式数据忽略了原始数据的一些细节，冈而能够适应一些“宏观” 研究，比如数据挖掘中的聚类和异类分析。 对于聚类问题，如何研究出高效的、能给出合理解释的、适用于表达式数据 的算法，仍将是今后研究人员工作的一个重点。在调研中，我们发现高维空间中 异类分析研究刚刚起步，困难较多。解决高维性带来的数据稀疏性问题。通常的 思路是采用子空间映射的方法。然而子空间的数目太多，如何从中选取出恰当的 呢? 我们提出了一个新的用于表达式数据的异类分析算法，该算法采用遗传机 制，能较好应对穷举法寻找子空间所带来的计算量爆炸问题。算法中采用基于距 离的方法来寻找异类数据，但也对该方法进行了改进，使之更为高效，同时对该 改进进行了理论上的分析。为了验证该算法的实用性，我们选取了酵母菌、人类 和淋巴瘤数据进行实验。实验一方面证明了该遗传算法的实用性，另一方面也验 证了我们所进行的改进的效率。从异类分析的角度看，该方法具有一定的普适性， 能够被用于其它高维数据的异类分析。 ( 2 ) 新的并行计算模型 已有的并行结构在处理双序列比对问题时有些困难，这是由于比对本身的 串行特征和超细粒度引起的。我们在调研当中，发现了一种新的并行计算模型 c e l lm a t r i x t ”能解决这一问题。该模型是由美国公司提出的，是一种典型的纳米 计算模型。该模型的基本单元是方形品格，平面上的晶格紧密相连，每个晶格从 相邻晶格得到输入，同时根据其自身内部的存储器设置得到结果，再将运算结果 输出到相邻晶格。 该模型虽然是一种全新的模型，但在其迄今为数不多的应用中已经出现了双 序列比对。我们的研究目的是进一步完善该结构上的算法实现和开销分析方法。 为此，我们在这种结构上介绍了已有的双序列比对算法并对其进行了完善，使其 能同时输出最佳比对和罚分。 对于这种结构，如何进行性能分析昵? 从算法的时空复杂性得到启发，我们 提出了对这种结构的性能分析方法，主要包括晶格数目开销和晶格延迟时间两方 面。晶格数目开销指的是所占用的晶格数目，这可以理解为空间复杂度。晶格延 迟时间，是指其内部主数据流或最长数据流所经过的晶格数目，这可以理解为时 间复杂度。晶格延迟时间可以简单等同于晶格延迟数目，这是因为所有的晶格都 是同构的，所需的处理时间都是基本相同的。以平衡分组选择网络为例，我们详 细介绍了分析的方法，然后对双序列比对算法也进行了分析。 双序列比对的实现来证明了该结构是可以用于生物计算的。问题是它能在多 中国科学技术大学博士学位论文 第1 章绪论 大程度上满足生物计算的需求呢? 这还有待于今后的进一步研究。可以看到，由 于d n a 序列的特性，每个核苷酸都可以由固定长度的二进制数表示，用该结构 来实现是非常自然的。因此，我们有理由相信，将来该结构必定对生物计算的发 展有促进作用。 此外，我 j 还研究了另一种l a r p b s ( l i n e a ra r r a y sw i t hr e c o n f l g u r a b l e p i p e l i n e db u ss y s t e m ) 模型，该模型有较好的通信性能。在对生物序列上的计算 研究时，我们将介绍一个在该模型上的多序列比对的并行算法。 ( 3 ) 生物序列上的计算问题 序列比对问题的主要难点在于多序列比对，由于该问题本身复杂，至今还没 有有效的算法。在并行算法的设计时，如何避免问题的串行特性呢? 我们注意到 已有的近似算法在处理过程中，可以采用分组的方式，这正好符合并行的原则。 我们提出了两个并行近似算法。一是在经典的s i m d c r e w 模型上，给出了一 个使用矿，t 个处理器，时间复杂度为o ( m + l o g k ) 的并行近似算法( 这里m 是序列 长度，k 是序列个数) ，与时间复杂度为o ( k 2 m 2 ) 的串行算法的相比，理论上达到 了线性加速。二是还结合新模型l a r p b s 的特点，首次给出了一个在l a r p b s 模型上的求解多序列比对问题的并行近似算法。它使用七2 m 个处理器，时间复杂 度为o ( m + l o g l o g d ) ，在理论上也达到线性加速，其中d 是序列两两比对的代价 值的最大值。特别是，o ( m + l o g l o g d ) 与序列个数k 无关，只与序列长度m 有关， 与前一个算法的时间复杂度相比大为简化，同时它也易于分析时间复杂度，在任 何情况下都适用。考虑到l a r p b s 模型t l 身的特点，将来可以用它来解决生物 信息学中的更多问题，得到更好的结果。关于该模型，我们将在第2 、4 、5 章中 详细介绍。 对于序列上的其它一些计算问题，我们也进行了调研。序列压缩是一类较困 难的问题，能否真正实现高效的压缩昵? 单倍型推导问题也是近年来的新兴热 点，现今的计算方法主要有基于组合优化的方法和基于统计的方法两大类。单倍 型推导问题已经开始走向实用，一些用于该问题的专用芯片已经出现。有理由相 信，单倍型推导问题本身有着巨大的研究价值和市场价值，将会对人类技术进步 产生不小的影响。当前，如何设计更精确的单倍型推导算法，具有重要的意义。 1 5 文献资源 为了便于调研、学习和研究，我们列出一些重要的经常发表算法研究成果的 电子文献资源、国际会议文献资源和纸介质文献资源( 学术刊物) 供参考。 ( 1 ) 电子文献资源 6 中国科学技术大学博士学位论文 第l 章绪论 a c m 电子文献资源数据库，i e e e 电子文献资源数据库，e l s e v i e r 电子文献 资源数据库，a c a d e m i c 电子文献资源数据库，s p r i n g e r 电子文献资源数据库， k l u w e r 电子文献资源数据库，中国学术期刊网，等。 ( 2 ) 国际会议文献资源 p r o c e e d i n g so fa c ma n n u a ls y m p o s i u mo nt h e o r yo fc o m p u t i n g ( s t o c ) ； p r o c e e d i n g so fi e e es y m p o s i u mo nf o u n d a t i o no fc o m p u t e rs c i e n c e ( f o c s ) ； p r o c e e d i n g s o fa c m s i a m s y m p o s i u m o nd i s c r e t e a l g o r i t h m s ( s o d a ) ； p r o c e e d i n g so fa c ms y m p o s i u mo np a r a l l e la l g o r i t h m sa n da r c h i t e c t u r e s ( s p a a ) ； p r o c e e d i n g so fa c mi n t e r n a t i o n a lc o n f e r e n c eo ni n f o r m a t i o nr e t r i e v a l ；p r o c e e d i n g s o f i f i pw o r l dc o m p u t e r c o n g r e s s o np a r a l l e l p r o c e s s i n g ；p r o c e e d i n g sio f i n t e m a t i o n a lc o n f e r e n c eo np a r a l l e la n dd i s t r i b u t e ds y s t e m s ；p r o c e e d i n g so fi e e e i n t e r n a t i o n a lc o n f e r e n c eo na l g o r i t h m s ，a r c h i t e c t u r e ，a n dn e t w o r k s ；p r o c e e d i n g so f i n t e r n a t i o n a lc o n f e r e n c eo np a r a l l e lp r o c e s s i n g ；p r o c e e d i n g so fa n n u a le u r o p e a n s y m p o s i u mo na l g o r i t h m s ；p r o c e e d i n g so fa n n u a ls y m p o s i u mo nc o m b i n a t o r i a l p a t t e r nm a t c h i n g ( c p m ) ；p r o c e e d i n g so fi n t e r n a t i o n a lw o r k s h o po na l g o r i t h m sa n d d a t a s t r u c t u r e s ；p r o c e e d i n g so fi n t e r n a t i o n a lc o n f e r e n c eo na l g o r i t h m sa n d a r c h i t e c t u r e sf o rp a r a l l e lp r o c e s s i n g ；p r o c e e d i n g so ft h ec o m p u t a t i o n a ls y s t e m s b i o i n f o r m a t i c s c o n f e r e n c e ，p r o c e e d i n g so ft h ei n t e r n a t i o n a lc o n f e r e n c e o n b i o i n f o r m a t i c s ，e t c ( 3 ) 纸介质文献资源( 学术刊物) c o m m u n i c a t i o n so fa c m ，j o u r n a lo fa c m ，a c mc o m p u t i n g s u r v e y s ， p r o c e e d i n g so fi e e e ，i e e et m n s o nc o m p u t e r s ，i e e et r a n s o np a r a l l e la n d d i s t r i b u t e ds y s t e m s ，j o u r n a lo fa l g o r i t h m s ，a l g o r i t h m i c a ，s i a mj o u r n a lo n c o m p u t i n g ，t h e o r e t i c a lc o m p u t e rs c i e n c e ，j o u r n a lo fc o m p u t e ra n ds y s t e ms c i e n c e ， i n f o r m a t i o np r o c e s s i n g l e t t e r s ，j o u r n a lo fp a r a l l e la n dd i s t r i b u t e dc o m p u t i n g ， p a r a l l e lc o m p u t i n g ，i n f o r m a t i o na n dc o m p u t a t i o n ，i n f o r m a t i o na n dc o n t r o l ，i b m r e s e a r c ha n dd e v e l o p m e n t ，j o u r n a lo fd i s c r e t ea l g o r i t h m s ，j o u m a lo fc o m p l e x i t y , i n t e r n a t i o n a lj o u r n a lo fp a r a l l e lp r o g r a m m i n g ，j o u r n a lo fd i s c r e t em a t h e m a t i c s