序列比对（20）基序发现问题的算法及实现代码

前文介绍了基序发现问题和中间字符串问题，本文给出了基序发现问题的具体算法和实现代码。

基序发现问题的简单算法及伪代码

本文将介绍基序发现问题的算法，并给出实现代码。

由于要遍历所有可能的起始位点，所以一种自然的想法是使用递归。但是为了配合后续的分支定界法，我们采用了树结构，并且进行DFS（深度优先搜索）。既然采用树结构，最简单的算法如下（伪代码）：

图1 引自《生物信息学算法导论》

图2 引自《生物信息学算法导论》

分支定界策略改进简单算法

上述简单算法的效率是非常低的，具体实验效果参见后文。效率低是由于树的顶点数量过大，遍历每一个顶点所需的总时间过长。鉴于此，可以采用一种分支定界策略有选择地跳过一些分支，即以某个顶点为根的分支树中的所有顶点都被跳过，从而可能大大提升效率。

用分支定界策略改进上述简单算法的伪代码如下：

图3 引自《生物信息学算法导论》

图4 引自《生物信息学算法导论》

实验效果

我们用《生物信息学算法导论》书中的两组序列进行实验，分别用简单算法（motifFinding_BF.exe)和分支定界法（motifFinding_BB.exe）去计算基序。 第一组序列（存储在identity.txt文件中，下面示例结果中用到）：

CGGGGCTATGCAACTGGGTCGTCACATTCCCCTTTCGATA TTTGAGGGTGCCCAATAAATGCAACTCCAAAGCGGACAAA GGATGCAACTGATGCCGTTTGACGACCTAAATCAACGGCC AAGGATGCAACTCCAGGAGCGCCTTTGCTGGTTCTACCTG AATTTTCTAAAAAGATTATAATGTCGGTCCATGCAACTTC CTGCTGTACAACTGAGATCATGCTGCATGCAACTTTCAAC TACATGATCTTTTGATGCAACTTGGATGAGGGAATGATGC

第二组序列（存储在mutated.txt文件中，下面示例结果中用到）：

CGGGGCTATcCAgCTGGGTCGTCACATTCCCCTTTCGATA TTTGAGGGTGCCCAATAAggGCAACTCCAAAGCGGACAAA GGATGgAtCTGATGCCGTTTGACGACCTAAATCAACGGCC AAGGAaGCAACcCCAGGAGCGCCTTTGCTGGTTCTACCTG AATTTTCTAAAAAGATTATAATGTCGGTCCtTGgAACTTC CTGCTGTACAACTGAGATCATGCTGCATGCcAtTTTCAAC TACATGATCTTTTGATGgcACTTGGATGAGGGAATGATGC

可惜的是，简单算法的效率过低，当序列增至7条时，简单算法用了半小时也没有结果，笔者就中断了运行。而分支定界法则很快就得出了结果，效率挺高的。

分支定界法的结果如下：

identity.txt文件中的7条序列计算基序

mutated.txt文件中的7条序列计算基序

具体代码

上文及前文都假定多条序列的长度是一样的，但是实际情况并不总是如此。代码实现过程中考虑到这一点，做了改进，使得多条序列不一致的情况下也可以用此代码来计算基序。