模序联配问题

• tmxk88122 发布于
• 1630 收藏

模序联配问题 寻找一条穿过编辑图的最长的块路径。 输入：两条序列u和v，并划分成大小为t的模序 输出：u和v的具有最大联配得分的模序联配，即：穿过编辑图的最长块路径。 考虑(n/t) * (n/t) 块对，每对块定义编辑图中的一个正方形区域，同时对每对模序计算联配得分βi,j。 Si,j表示U的前i个模序与v的前个模序之间的最优模序联配得分。那么： σblock是插入或删除整个模序的罚分。 Si,...