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

最短超序列问题的时间优化 李昭杨琪祝明发 中国科学院计算技术研究所北京2704信箱(100080) 摘要测定基因组序列是生物信息处理中一项非常重要的任务，当前使用的测序方法中最 为常用的方法就是随机测序法(ShotgunSequence)．这种方法的关键问题是需要通 过大量短片断之间的重叠部分将所有片断拼接起来形成正确的超序列，也称为最短 超序列问题(Shortest Problem，SSP)．解决这种问题常用的算法是贪婪 Super-string 算法(GreedyAlgorithm)，贪婪算法的时间复杂度为cX矗2)。本文介绍了一种对贪婪 算法的并行优化方法，通过理论分析，在理想情况下这种并行方法可以获得min(n2／lgn， np)的加速比(其中，l为拼接问题的规模，即处理的片断数量，np为实际可以使用的 处理器个数)．但是在一般情况下，许多问题限制了这种并行方法的效率．通过对 并行方法的实现和实际数据的测试，这种并行方法能够在一定的程度上降低贪婪拼 接算法的时间复杂度． ’ 关键字生物信息处理，序列拼接，SSP问题，贪婪算法，并行优化 l基本算法介绍 随机测序法(ShotgunSequencing)是当前使用广泛的DNA序列的测序方法，这种方法首 先将多条冗余的基因序列打断成大小不一，相互重迭的片段；然后通过测序仪读出这些片断； 最后，计算机通过片断之间的重叠部分将所有的片断拼接起来获得完整的基因组序列。随机 测序方法中的序列拼接问题是一种最短超序列问题(Shortest Problem，SSP)给定 Super-string 一个序列片断集合，．_所，五，…，石}，我们希望发现一个最短的超序列s，使得集合F中的所有 序列片断都是S的子序列。可以证明SSP问题是NP完备性问题【l】。 要解决NP完备性问题，必须采用一种近似最优的算法来降低其时间复杂度。解决SSP 以做如下的假定：在0i，，≤n且f≠，的情况下，石勘；对其中任意两个序列石，石，可以写成 O。贪婪算法的具体描述如图l所示，从算法描述中可以简单的推算出贪婪算法的时间复杂度 。 为O(n2)。 A丁卜{Z，五，…，Z)，S卜西’ Bwhile T≠西，do for with s，，∈T max{overlap(s，，)}O=f possible) (a)ifs≠fJandftO merge uvw； removesfrom s Co)ifs=t 7’；addtoS： Cwhen the