Motif Finding问题的分布式参数算法

基于从DNA序列形成k分图的图理论算法和查找k-clique的理论算法,设计与实现了对Motif Finding问题求解的分布式参数算法。该算法的主要特点是:采用新的1-3树分枝算法并实现分布式计算机制,即任务可以随着计算过程的展开在每一阶段不断地分解并分布到不确定数量的申请参与计算的客户机上,服务器端负责任务均衡与结果整合。实验结果表明:分布式参数算法充分利用多台机器协同计算,能够正确、高效地得到计算结果,为求解生物计算中难解的Motif Finding问题提供了有效的解决手段。

Distributed parameterized algorithm for Motif Finding

Based on the graph-theoretic algorithm,which is used to generate k-partite graph from DNA sequences,and a theoretic algorithm which is used to search k-clique in k-partite graph,a new distributed parameterized algorithm is designed and implemented to solve Motif Finding problem.The main characteristics of this algorithm are the introduction of 1?3 tree branching algorithm and the implementation of distributed mechanism,i.e.,task can be constantly decomposed into several tasks as program proceeding at each phase,and then these tasks are distributed to several client computers which is applied for participation of calculation.On the server,the tasks are distributed and balanced as well as the results are received and combined.Experimental results show that this distributed parameterized algorithm is correct and efficient since it makes full use of computing capability of many computers,and provides an effective approach to solving the difficult problems in biocomputing such as Motif Finding.