On finding minimal absent words.
On finding minimal absent words.
复制标题
DOI：
10.1186/1471-2105-10-137
复制
发表时间：
2009-05-08
影响因子：
3
通讯作者：
Rodrigues JM
中科院分区：
文献类型：
--
作者：
Pinho AJ;Ferreira PJ;Garcia SP;Rodrigues JM
最近解决了在 DNA 数据中寻找最短缺失单词的问题，并描述了其解决方案的算法。已经注意到，较长的缺席词也可能令人感兴趣，但现有算法仅通过简单地扩展最短的缺席词来提供通用的缺席词。我们展示了缺席词如何与数据的重复和结构相关，并定义了一类新的、更大的缺席词，称为最小缺席词，它仍然捕获了最近作品中引入的最短缺席词的基本属性。这个新类的单词是最小的，因为如果删除它们最左边或最右边的字符，那么生成的单词就不再是缺席的单词。我们描述了一种生成最小缺失单词的算法，该算法在实践中以近似线性的时间运行。该算法的实现可在 上公开获得。因为我们提出的最小缺席词集比最短缺席词集大得多，所以它对于需要更丰富的缺席词的应用程序可能更有用。尽管如此，最小缺失词的数量仍然是可控的，因为它最多与字符串大小线性增长，这与呈指数增长的一般缺失词不同。该算法及其所依赖的概念都为缺失单词的结构提供了更多的线索，并补充了该主题的现有研究。
The problem of finding the shortest absent words in DNA data has been recently addressed, and algorithms for its solution have been described. It has been noted that longer absent words might also be of interest, but the existing algorithms only provide generic absent words by trivially extending the shortest ones. We show how absent words relate to the repetitions and structure of the data, and define a new and larger class of absent words, called minimal absent words, that still captures the essential properties of the shortest absent words introduced in recent works. The words of this new class are minimal in the sense that if their leftmost or rightmost character is removed, then the resulting word is no longer an absent word. We describe an algorithm for generating minimal absent words that, in practice, runs in approximately linear time. An implementation of this algorithm is publicly available at . Because the set of minimal absent words that we propose is much larger than the set of the shortest absent words, it is potentially more useful for applications that require a richer variety of absent words. Nevertheless, the number of minimal absent words is still manageable since it grows at most linearly with the string size, unlike generic absent words that grow exponentially. Both the algorithm and the concepts upon which it depends shed additional light on the structure of absent words and complement the existing studies on the topic.
登录
查看更多内容
影响因子：
2.5
作者：
MCCREIGHT, EM
通讯作者：
MCCREIGHT, EM
影响因子：
3.7
作者：
Acquisti, Claudia;Poste, George;Curtiss, David;Kumar, Sudhir
通讯作者：
Kumar, Sudhir
影响因子：
3
作者：
Herold, Julia;Kurtz, Stefan;Giegerich, Robert
通讯作者：
Giegerich, Robert
影响因子：
1.1
作者：
UKKONEN, E
通讯作者：
UKKONEN, E
影响因子：
1.6
作者：
MANBER, U;MYERS, G
通讯作者：
MYERS, G