摘要
最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串。这个问题是一个NP-完全问题。目前已有一些方法对此进行了研究。通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题。最后给出了几个实例。
The shortest common superstring problem （SCS） is to find the shortest possible string that contains every string in a given set as substrings. As the problem is NP-complete. This days, there are many methods to deal with it. An approximation algorithm based on greedy algorithm and Hamiltonian path is proposed to deal with the shortest common superstring problem by analyzing the every substring. One obvious application for the problem is sequenced DNA fragments. Another is data compression. Finally, some examples are given.
出处
《计算机工程与设计》
CSCD
北大核心
2007年第8期1757-1758,1761,共3页
Computer Engineering and Design
基金
云南省教育厅自然科学基金项目(02ZY093
6Y0070D)
昆明学院校管科研基金项目(2006Z002)
关键词
最短公共超串
覆盖
算法
贪婪算法
哈密尔顿路
shortest common superstring
overlap
algorithm
greedy algorithm
hamiltonian path
