前文介绍了基序发现问题和中间字符串问题,本文给出了基序发现问题的具体算法和实现代码。
本文将介绍基序发现问题的算法,并给出实现代码。
由于要遍历所有可能的起始位点,所以一种自然的想法是使用递归
。但是为了配合后续的分支定界法,我们采用了树
结构,并且进行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条序列计算基序
上文及前文都假定多条序列的长度是一样的,但是实际情况并不总是如此。代码实现过程中考虑到这一点,做了改进,使得多条序列不一致的情况下也可以用此代码来计算基序。