生物序列比对算法研究

《生物序列比对算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要随着多种基因组计划的逐步实施，产生的有关核酸、蛋白质序列和结构的“海量”数据，对生物信息学研究既是机遇也是挑战．企图完全通过生物实验的方法来确定所有序列的结构、功能非常困难，同时也不经济。因而利用序列比对寻找与功能未知序列同源的已知序列，用己知预测未知就显得尤为重要。在这个过程中，提高序列比对的有效性、减少运行时间和存储空间具有重要的理论意义和实用价值。本文利用动态规划，概率统计等方法对多序列比对问题进行了研究．在理论方面：提出了相对多序列比对差异性、压缩矩阵等概念；对算法中部分迭代公式进行了归纳、抽象．给出了基于压缩矩阵

2、的表达递推形式。在算法方面：设计了具有监控机制的多序列比对遗传算法；提出了多序列比对的刹面广义相关隐马尔可夫模型。主要工作和研究成果如下：1．为了描述一个多序列比对是否具有某种特征统计特性，提出了多序列比对相对于某己知特征统计矩阵的代价概念，并给出了具体定义．在此基础上，定义了一组多序列比对差异性量化指标，用于种群多样性判别。2．针对多序列比对的遗传算法中缺少利用已知种群先验信息的问题，提出了一种利用种群多样性监控、指导多序列比对的遗传算法执行步骤的比对算法．结果表明，新算法在避免局部最优解方面有较好的表现，且比对结果宜具有区

3、块性。3．针对剖面隐马尔可夫模型中状态转换及符号输出的特性，以及目前基于此模型的迭代表达公式过于繁琐的问题，提出了压缩矩阵、向前、向后概率向量等概念。其中状态压缩矩阵是由一个阶数为3(L+1)×3(L+1)的矩阵压缩后得到的阶数为9×(￡+1)的矩阵(L为正整数)。且保留原有矩阵的全部信息。显然，原矩阵阶数越大，压缩矩阵节省的存储空间就越多，为编程实现提供了节省存储空间的理论依据．此外，给出了基于压缩矩阵表示的递推关系式，使迭代过程直观化、模块化。易于编程实现．4．针对割砸隐马尔可夫模型没有考虑输出的观测字符依赖前一时刻输出的

4、观测字符，而生物序列中的字符实际上又不是相互独立的这一矛盾，将语音识别领域的双重分次约束隐马尔可夫模型用于多序列比对，建立了用于多序列比对的剖面广义相关隐马尔可夫模型，新模型更符合生物序列固有的特性。5，设计并实现了一个基于Windows操作系统的序列比对系统。该系统采用VB6．0和EXCEL进行开发·系统界面友好，操作简单．有便捷的工具栏、系统菜单、帮助等模块。为研究、利用多序列比对人员提供了一个平台．关键词：生物信息学，多序列比对，遗传算法，跨马尔可夫模型，剖面隐马尔可夫模型AbstractDataconcerningwi

5、thsequencesandstructuresofDNAandproteinhasascendedexponentiallynowadays,withthegraduallyimplementingoftheHumanGenuineProjectThehugebioinformaticedatabasebringsupa∞Vc"challengetotheexistedmethodsandabilityofdataprocess吨．TheworkOnbiolnformalicemainlyaimsatdiggingoutth

6、evaluablebioinformatics00dis∞VcffunctionalandstructuralknowledgerationallyinDNAandproteinsequences．Presentlythetechniquesofgenelocating．repetitivesequencesearch,andgenegroupsplicingareallbasedOnthesequencealigment,whichdemonstratesthesigl吐矗髓n∞ofimprovingsequencealig

7、mentveracityandrunningefficiency．Mainresearchesinthepaperareoomultiplesequencealigmembyemployingdynamicpro舢ming．probabilityandstatistics．The∞州譬州佃sofdifferencesandcompressmatrixformultiplesequencealigmentaredescribedfirst．Andthee,so嘶ofgenerallyexpression*aleprovideda

8、fterboththeinductionandtheabstractionareappliedto对golithm缸multipleⅫ[uellccaligngnLAgoneralized-mutualityProfileHMMmodel缸presentedalso．Last