最短超序列问题的时间优化

摘要：

测定基因组序列是生物信息处理中一项非常重要的任务,当前使用的测序方法中最为常用的方法就是随机测序法(ShotgunSequence).这种方法的关键问题是需要通过大量短片断之间的重叠部分将所有片断拼接起来形成正确的超序列,也称为最短超序列问题(ShortestSuper-stringProblem,SSP).解决这种问题常用的算法是贪婪算法(GreedyAlgorithm),贪婪算法的时间复杂度为O(n2).本文介绍了一种对贪婪算法的并行优化方法,通过理论分析,在理想情况下这种并行方法可以获得min(n2/lgn,np)的加速比(其中n为拼接问题的规模,即处理的片断数量,np为实际可以使用的处理器个数).但是在一般情况下,许多问题限制了这种并行方法的效率.通过对并行方法的实现和实际数据的测试,这种并行方法能够在一定的程度上降低贪婪拼接算法的时间复杂度.

关键词： 生物信息处理 序列拼接 SSP问题 贪婪算法 并行优化 基因组序列

作者: 李昭 杨琪 祝明发

作者单位: 中国科学院计算技术研究所北京2704信箱,100080

会议类型: 国内会议

会议名称: 中国电子学会第八届青年学术年会暨中国电子学会青年工作委员会成立十周年学术研讨会

会议地点: 合肥

会议语种:中文

页码: 779-785

在线出版日期: 2002-08-13（万方平台首次上网日期，不代表论文的发表时间）