t-coffee 序列比对

《t-coffee 序列比对》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第4期计算机应用与软件V01．25No．42008年4月ComputerApplicationsandSoftwareApr．2008多序列比对软件T—Coffee的并行化设计与实现靳新骆志刚蒋晓舟王金华张雯(国防科学技术大学并行与分布处理国家重点实验室湖南长沙410073)摘要T—Coffee是广泛用于核酸或氨基酸的多序列比对工具。它通过生成基本信息库，扩展库，生成指导树，渐近式比对四个阶段来完成多序列的比对。分析了T—Coffee串行算法及其复杂度，并提出了基于SMP机的并行化版本。目标

2、是使其充分并行化，实验结果表明它明显的提高了性能，并得到了很好的相对加速比。关键词全局比对局部比对渐近式算法共享内存多处理机DESIGNANDIMPLEMENTATIoNoFPARALLELISMoFMULTIPLESEQUENCEALIGNMENTSoFTWARET-CoFFEEJinXinLuoZhigangJiangXiaozhouWangJinhuaZhangWen(NationalLaboratoryofParallelandDistributedProcessing，NUDT，Chang

3、sha410073，Hunan，China)AbstractT—Coffeeisthemostwidelyusedtoolforaligningmultipleproteinornucleotidesequences．Thealignmentisachievedviafourstages：primarylibrarygeneration，extendedlibrarygeneration，guidetreegenerationandprogressivealignment．Thecomplexity

4、ofT—Coffeese—quencealgorithmisanalyzed，andaparallelversionforT—CoffeebasedonSMPispresentedwithanaimtorealizedfullparallelism．Theexper+imentalresultsshowthattheparallelversionimprovestheperformancesignificantly，andaconsiderablespeedupoverthesequentialT—

5、Coffeeisachieved．KeywordsGlobalalignmentLocalalignmentProgressivealgorithmSMP0引言1T-Cofee串行算法多序列比对是分子生物学中重要的分析工具。它可用T—Coffee是一种新的准确率高的多序列比对算法，由Jaap于探测新序列与已知序列家族的同源性，预测新序列的二级Heringa等四人于2000年提出。传统的多序列比对通常由序列和三级结构，蛋白质家族中结构或功能的相似片断。随着测两两比对产生距离矩阵、生成系统发育树、渐近算

6、法的全局比对序的自动化使得新序列以指数级别增长，人们对快速高效的三部分组成。而T—Coffee综合了全局和局部比对信息，并增加多序列比对算法的需求越来越迫切。目前已产生了几种多了序列的位置信息，提高了多序列比对的敏感性和准确率。其序列比对软件，如MSA，PRALINE，MAFFT，ClustalW⋯，T．流程如图1所示。Coffee等，这些算法的时间复杂度都非常高。其中，T．Col-fee是新产生的一种方法，与前几种方法相比，它综合了全局和局部比对及位置信息，提高了准确率和敏感性，但同时也增加了它的

7、时间复杂度。缓存和并行化的策略通常可以降低这些算法的时间复杂度，提高计算吞吐量。ClustalW目前已产生了多种并行化版本，如SGI的ClustalW商业版本，基于Pc集群的pClust．alWJ，基于消息通信的ClustalW—MPI，这些算法都在不同环境下、不同程度上提高了ClustalW的效率，而T-Coffee目图1T—Coffee的逻辑流程前还未实现并行化。生成基本比对信息库分别对输入序列进行两两全局和局本文提出了基于SMP的T—Coffee并行化算法，它将T—Cof-部比对，从而形成全局

8、比对信息库和局部比对信息库，然后对这fee按功能分成四个阶段，分别实施并行化策略，这样大大降低了T．Coffee的时间复杂度。它可以用于服务器上执行，以提供收稿日期：2006—08—11。靳新，硕士生，主研领域：计算机应用技高效快速的多序列比对服务。术，生物信息学。222计算机应用与软件2008丘两个库进行组合，产生一个基本比对信息库，作为下一步的输由于j·loop循环大小可变，我们采用OpenMP的“dynam—入。这一步复杂度为O(NL)，N是输入序列条数，L是序