论文部分内容阅读
在生物序列中查找基序是生物信息学中一个重要的计算问题，人们针对这一计算问题提出了多种模型和算法。由于真实生物序列数据的复杂性，其中有许多是比强信号基序更难提取的弱信号基序。本文作者重点研究了适合于模拟弱信号基序查找的植入(l，d)基序问题(PMP)和扩展植入(l，d)基序问题(EMP)模型；并归纳分析了基序查找的基本方法、策略和基序模型，指出了各种策略和模型的优势与不足。在此基础上对现有的基于植入基序查找问题模型的主要弱信号基序查找算法进行了分析和实验评估。针对弱信号基序查找问题作者提出了一种基于统一投影和邻居桶聚集提炼策略的基序查找算法UPNT(Uniform Projection withNeighbourhood Thresholding)。在UPNT算法中，利用统一投影策略有效减少了投影数目，并使用邻居桶聚集提炼的策略大大减少了提炼桶的数目。作者进一步使用背景分布均衡与非均衡的合成(l，d)序列两套数据集对算法性能进行测试和分析，实验结果表明：UPNT在成功率和运行时间上的综合性能优于Random Projection、AGGREGATION和Uniform Projection等投影算法，具有更强的适用性。在生物序列中还存在很大一部分带间隔的二分体基序，二分体基序中可能其中一个子基序是弱信号，但它们的组合却具有强统计显著性。作者针对二分体基序的特点提出了一种基于Box-Links枚举统计给候选基序计分的二分体基序查找算法DMDB(Dyad Motif Discoverybased on Box-Links)，并通过实验验证了算法的有效性。最后，作者对生物序列中的基序查找问题进行了总结，并讨论了该方向上尚未解决的问题和发展趋势。