Skip to content

Latest commit

 

History

History
62 lines (32 loc) · 1.49 KB

README.md

File metadata and controls

62 lines (32 loc) · 1.49 KB

原理

举例说明:A=GGATCGA,B=GAATTCAGTTA

第一步:初始化LD矩阵

公式一

若ai=bj,则LD(i,j)=LD(i-1,j-1)

若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1

第二步:利用上述的公式一,计算第一行

第三步,利用上述的公示一,计算其余各行

第四步,定位在矩阵的右下角

第五步,回溯单元格,至矩阵的左上角

若ai=bj,则回溯到左上角单元格

若ai≠bj,回溯到左上角、上边、左边中值最小的单元格,若有相同最小值的单元格,优先级按照左上角、上边、左边的顺序

若当前单元格是在矩阵的第一行,则回溯至左边的单元格

若当前单元格是在矩阵的第一列,则回溯至上边的单元格

依照上面的回溯法则,回溯到矩阵的左上角

第六步,根据回溯路径,写出匹配字串

若回溯到左上角单元格,将ai添加到匹配字串A,将bj添加到匹配字串B

若回溯到上边单元格,将ai添加到匹配字串A,将_添加到匹配字串B

若回溯到左边单元格,将_添加到匹配字串A,将bj添加到匹配字串B

搜索晚整个匹配路径,匹配字串也就完成了

A:GGA_TC_G__A

B:GAATTCAGTTA

成果物