EMS1: ANELEGANT ALGORITHM FOR EDIT DISTANCE BASED MOTIF SEARCH
EMS1: ANELEGANT ALGORITHM FOR EDIT DISTANCE BASED MOTIF SEARCH
复制标题
DOI：
10.1142/s0129054113500159
复制
发表时间：
2013-06-01
影响因子：
0.8
通讯作者：
Nicolae, Marius
中科院分区：
文献类型：
--
作者：
Pathak, Sudipta;Rajasekaran, Sanguthevar;Nicolae, Marius
基序是在DNA/蛋白质序列中发现的具有生物学意义的模式。给定一组生物序列，识别基序的问题是非常具有挑战性的。这个问题在计算生物学中得到了很好的研究。通过实验过程识别基序是非常昂贵和耗时的。这是影响计算生物学家想出新的计算方法来预测基序的因素之一。在文献中提出了几个基序模型，并为每个模型设计了许多算法。三种流行的motif模型是(1,d)-motif搜索或种植motif搜索（PMS），简单motif搜索（SMS）和基于编辑距离的motif搜索（EMS）。对于PMS和SMS，已经提出并实现了几种算法。另一方面，尽管文献中存在一些针对EMS问题的算法，但这些算法的实现是未知的。这主要是因为所提出的算法比较复杂。在本文中，我们提出了一种优雅的EMS算法。我们已经实现了该算法，并将其与其他14种算法在灵敏度和特异性方面进行了比较。实验结果表明，新算法在实践中具有很强的竞争力。
Motifs are biologically significant patterns found in DNA/protein sequences. Given a set of biological sequences, the problem of identifying the motifs is very challenging. This problem has been well studied in computational biology. Identifying motifs through experimental processes is extremely expensive and time consuming. This is one of the factors influencing computational biologists to come up with novel computational methods to predict motifs. Several motif models have been proposed in the literature and for each model numerous algorithms have been devised. Three popular motif models are (l, d)-motif search or Planted Motif Search (PMS), Simple Motif Search (SMS), and Edit-distance based Motif Search (EMS). For PMS and SMS several algorithms have been proposed and implemented. On the other hand, even though some algorithms exist in the literature for the problem of EMS, no implementations of these algorithms are known. This is mainly because the proposed algorithms are complex. In this paper we present an elegant algorithm for EMS. We have implemented this algorithm and compared it against 14 other algorithms in terms of sensitivity and specificity. Our experimental results indicate that the new algorithm is very competitive in practice.