High-performance exact algorithms for motif search.
High-performance exact algorithms for motif search.
复制标题
DOI：
10.1007/s10877-005-0677-y
复制
发表时间：
2005-10-01
影响因子：
2.2
通讯作者：
Schiller, Martin
中科院分区：
文献类型：
--
作者：
Rajasekaran, Sanguthevar;Balla, Sudha;Schiller, Martin
目的：人类基因组计划产生了大量的生物数据。需要新的计算技术从这些数据中提取有用的信息。其中一种技术是寻找在许多序列（也可能在许多物种）中重复的模式。在本文中，我们研究从生物数据中识别有意义的模式（即模体）的问题，即模体搜索问题。方法：模体搜索问题的一般版本是 NP 难的。文献中已经提出了许多算法来解决这个问题。许多这些算法都属于启发式算法的范畴。我们在本文中专注于精确算法。特别是，我们专注于两个不同版本的主题搜索问题，并为它们提供精确的算法。结果：在本文中，我们提出了两个版本的主题搜索问题的算法。我们所有的算法都很优雅，并且只使用数组这样简单的数据结构。对于本文中描述为问题 1 的问题的第一个版本，我们提出了一种基于简单排序的算法，SMS（简单主题搜索）。该算法已被编码并得到了实验结果。对于问题的第二个版本（论文中描述为问题 2），我们提出了两种不同的算法——确定性算法（称为 DMS）和随机算法（蒙特卡洛算法）。我们还展示了如何并行化这些算法。结论：本文提出的所有算法都是对生物序列数据中这些版本的基序搜索的现有算法的改进。所提出的算法在实践中具有良好表现的潜力。
OBJECTIVE: The human genome project has resulted in the generation of voluminous biological data. Novel computational techniques are called for to extract useful information from this data. One such technique is that of finding patterns that are repeated over many sequences (and possibly over many species). In this paper we study the problem of identifying meaningful patterns (i.e., motifs) from biological data, the motif search problem.METHODS: The general version of the motif search problem is NP-hard. Numerous algorithms have been proposed in the literature to solve this problem. Many of these algorithms fall under the category of heuristics. We concentrate on exact algorithms in this paper. In particular, we concentrate on two different versions of the motif search problem and offer exact algorithms for them.RESULTS: In this paper we present algorithms for two versions of the motif search problem. All of our algorithms are elegant and use only such simple data structures as arrays. For the first version of the problem described as Problem 1 in the paper, we present a simple sorting based algorithm, SMS (Simple Motif Search). This algorithm has been coded and experimental results have been obtained. For the second version of the problem (described in the paper as Problem 2), we present two different algorithms--a deterministic algorithm (called DMS) and a randomized algorithm (Monte Carlo algorithm). We also show how these algorithms can be parallelized.CONCLUSIONS: All the algorithms proposed in this paper are improvements over existing algorithms for these versions of motif search in biological sequence data. The algorithms presented have the potential of performing well in practice.