需求分析
本程序中序列就是字符串,两者表达的意思相同。
本程序最终所要实现的功能:
在多个字符串中查找指定长度的具有一定模式匹配(该匹配可以是子字符串完全匹配或者是允许个别几个字符不匹配(不匹配的位置可以人为指定))的子字符串,并输出所有满足要求的子序列。
具体问题描述:
1、有一组字符串,每个字符串的长度相等为w(但w不确定为何值),字符串元素由{A , T , C , G}四个字母组成。字符串组的来源可以是文本格式或其他(不限);
2、寻找其中满足一定匹配模式的指定长度L(可自己指定)的子串。
表达方式:
序列是由 { A, C, T, G } 四个字母构成的。例如对于以下两条序列(字符串):
: A T T A G T C A T
: A T T G A C G C A
当寻找长度为3,允许的不匹配度为0时, “A T T” 就是所要找的子字符串。当要求寻找长度为4,允许的不匹配度为1时,A T T A 和A T T G就是所要找的子字符串。
定 义:
(1)给定一组序列{ },其中n为输入的序列个数。 , ,w为序列的长度。
(2)将一段长度为L的子序列转化为点,即 ,i指序列,j指第i条序列上子序列(子字符串)开始的位置。
例如:对于上面的两条序列 (当L取值为3时)有:
: ATT--- TTA--- TAG--- AGT--- GTC---- TCA---- CAT-----
:ATT--- TTG--- TGA--- GAC--- ACG--- CGC---- GCA---
(3)距离 ,如果 ,则 ,否则 。
例如:对于上面序列的点 和点 来说,有 (即不相等的字符的个数)
(4)父节点parent( ) :对于 上的点 而言, 上的点都为它的父结点。
(5)邻节点neighbor( ):对于 上的点 而言,只有 上的节点成为它的邻节点。
具体步骤:分为两个子程序。
子程序一:
(1) 输入一组序列 (n可以自己指定)
(2) 从第一条序列开始,定义节点 。
(3) 对于其他序列,重复执行步骤2。直到第n条序列。
(4) 对于第一条序列上的第一个点 (将其放入集合 中,即 ),检查该点与其它序列上的每个点的距离 , 如果 ,则将 加入 ,即有 ,其中i指第i条序列,j指在第i条序列上节点开始的位置。对第二条到第n条序列上的节点重复进行与点 的距离比较,满足条件就加入,从而得到最终的集合 。
(5) 对于第一条序列上的其它点,重复执行步骤4,得到其它点所对应的集合 。
子程序二:
(1) 对于每一个 。
(2) 按顺序查找它包括的第二条、第三条、……、第n条序列上的节点的父节点列表(parentlist ,其中j指在 中的第二条序列上的点)。并且在第n条序列的节点的父节点列表中,统计每个节点所代表的子字符串中相应位置出现频率最高的字母,从而得到最终想要的结果子序列并进行输出。
注:通过递归调用得到节点 的父节点列表parentlist :当节点 与其邻点的距离小于等于2d时,将邻点及其父节点列表加入节点 的父节点列表parentlist 。同时比较节点 与邻点的父节点列表中的其它节点 的距离,如小于等于2d,则保留,否则删除此节点 与它的父节点列表parentlist 。对于第一条序列上的节点其父节点列表为它本身。
跳出递归循环的条件:当某一条序列上的所有点 的邻点都不满足条件时、或当程序执行到最后一条序列时。
(3)对于其他 ,重复步骤2。