可变剪接是指从一种前体mRNA(Pre-mRNA)中产生不同mRNA剪接型(异构体)的过程。它对真核生物中蛋白质组多样性具有重要贡献,并且使得蛋白质异构体的表达受到更多调控信号的调节。研究基因的可变剪接对理解真核生物基因调控具有十分重要的意义。文章首先归纳了可变剪接研究中常用的cDNA-基因组联配计算的基本方法,提出了设计高效可变剪接搜索算法的策略,即通过对cDNA数据库的联配搜索,并结合基因的已知剪接信息来预测可能存在的其他剪接模式。以这种策略为指导,本文开发了两种新的可变剪接搜索算法:以BLAST为核心的ASA(Alterntive Splicing Assembler)算法,以及一种高效可变剪接搜索算法——ASDT(Alternative Splicing Discover Tool)。ASA算法采用图论方法对BLAST计算结果进行计算分析来获得剪接模式。ASA在计算方法上采用了分段策略,即先在已知剪切型上定位,而后修补未匹配部分。这种计算策略不仅符合可变剪接搜索算法的目的,也极大地提高了ASA的运算速度。在计算结果可靠性方面,与ASDB数据库比较结果显示,ASA的可靠性达到了现有公开数据库的水平。对ASDT算法的研究则是在继承传统cDNA-基因组联配计算策略的基础上,从最底层联配计算的研究开发为切入点,通过开发多种辅助算法进行的。这些辅助算法包括截断快速散列表与增强后缀数组相结合的完全匹配片断搜索算法,全新的块联配延伸算法,全新的K最长参考路径算法,以及借鉴GMAP的“三明治”算法,结合Zhang等人提出的贪婪算法进行精确联配和调节剪接位点。这些算法使得ASDT的计算速度能够达到或超过现有的cDNA-基因组联配算法。实验显示其计算速