论文部分内容阅读
最近子串问题(CSP问题)是生物信息学中一个具有广泛应用的NP-难问题。它存在多项式时间近似方案(PTAS算法)。
本文利用参数复杂性理论，证明CSP问题的PTAS算法的计算复杂性下界。文中得出以下重要结论：除非指数时间算法假设(ETH 假设，即SNP类中存在次指数时间不可解的搜索问题)是错误的，否则CSP问题不存在运行时间为f(1/ε)|x|。(f为任意函数，|x|为输入实例的大小)的PTAS算法。这一结论排除了CSP问题具有有效的PTAS算法的可能性。因此，对于较小的近似误差界ε>O而言，已有文献中对CSP问题的PTAS算法的研究不大可能推导出对CSP问题的实际有效的PTAS算法。
根据上述结论，在单机上已不大可能解决CSP问题。因此本文考虑采用分布式计算求解。文中提出了一种新的分布式任务建模方法——任务树，并应用任务树的概念设计了两个有效的CSP问题的分布式算法：分布式精确算法和分布式PTAS算法。最后，文章还设计了一个基于任务树的生物信息学分布式计算平台，用于求解所有可以用任务树进行任务建模的问题。