针对基因选择性剪接的多序列比对算法研究.pdf

清华大学学报(自然科学版)年第卷第期
ISSN100020054200141928ö32
CN1122223öNJTsinghuaUniv(Sci&Tech),2001,Vol.41,No.91112114

针对基因选择性剪接的多序列比对算法研究

计宏凯,周晴,闻芳,季梁

(清华大学自动化系,北京100084)

摘要:为对真核基因的选择性剪接形式进行准确、快速、义。多序列比对是进行上述研究的重要工具[1～5]。本
有效的研究,提出了一种启发式多序列比对算法。该算法借文提出了一种针对基因选择性剪接的多序列比对算
助引导树启发序列之间的两两段对段比对,通过建立序列相法。该算法根据序列之间的相似性构造引导树,借助
似性估计模型,给出了一种由序列间相同词数估计序列相似引导树启发序列间的两两比对。对引导树构造方法
程度的方法。利用这种方法构造引导树,大大缩短了其构造
的改进和段对段比对[5]的引入,使算法运行时间大
时间。通过采用序列间的段对段比对,克服了间隙罚分问题,
大缩短也使比对结果能够更准确地反映基因的选
更准确地反映了真核基因的选择性剪接形式。引导树构造方,
择性剪接形式。
法的改进和快速局部比对算法的采用,使得算法运行速度大
大高于一般算法。该算法为真核基因的选择性剪接研究提供1基本原理
了一种新的有效途径。
1.1段对段比对
关键词:多序列比对;选择性剪接;引导树;段对段比对
对基因的选择性剪接比对而言,通常两个外显
中图分类号:Q811.4
子在DNA上的间隙比较大,而且间隙的变化范围
文章编号:100020054(2001)0920111204文献标识码:A
也比较大,因此寻找合适的间隙罚分策略比较困难。
我们采用了段对段比对解决以上问题。所谓段,就是
Researchonmultiplealignmentsfor无间隙的高分值局部比对片断。如果多个无间隙高
alternativesplicing分值比对片断能够在一个比对结果中同时出现,则
JIHongkai,ZHOUQing,WENFang,JILiang称它们是一致的。段对段比对给每个片断赋予一定
(AutomationDepartment,TsinghuaUniversity,的分值,它的优化目标是寻找一组一致的高分值局
Beijing100084,China)
部比对片断,使它们的分值和达到最大。这种比对方
Abstract:Aheuristicalgorithmformultiplealignmentwas
式避开了间隙罚分问题,适用于间隙较大,间隙变化
developedtomoreeffectivelystudyalternativesplicingpatternsof
[6]
eukaryoticgenes.Segment2to2segmentalignmentisguidedbya范围也较大的情况。另外,通过采用BLAST寻找
guide2tree.Thetimeforconstructingtheguide2treeisreduced高分值局部比对片断,多序列比对算法的速度得到
remarkablybyadoptingasimilarityestimationmodelwhich
了较大的提高。
estimatesthesimilaritiesbetweensequencesfromthetotalnumber
ofhits.Thesegment2to2segmentalignmenteliminatestheproblem1.2引导树的构造
introducedbythe“gap”whichexitsintraditionalalignmentssothat
alternativesplicingpatternsarerevealedmoreprecisely.Thenew1.2.1序列相似性估计模型
methodforconstructingtheguide2treeandthebasiclocalalignment
假设两条核酸序列长度分为有一段含
searchtoolincreasethealgorithmspeedrelativetoothermultipleL1,L2
alignmentalgorithms.Thisalgorithmisanewwaytostudy有N个碱基的共同区域。若它们有多段共同区域,
alternativesplicing.也将用一段来等效。用N来衡量两序列的相似程

Keywords:multiplealignment;alternativesplicing;guide2tree;度,N越大则两序列的相似程度越高。定义序列中
segment2to2segmentalignment
相邻的M个碱基构