基于序列比对算法的地质剖面图自动生成

摘要

为了能够由计算机自动生成正确的地层分界线,并能处理复杂的地层尖灭和透镜体现象,借鉴生物信息学中生物序列的比对算法,设计了基于动态规划思想的地层序列比对算法.舍弃替换矩阵采用更灵活的计分函数.为了处理透镜体,将被分割的主层进行合并比对,采用分裂另一个比对样本的技术来实现;为避免地层的盲目分裂行为,指定地层分裂阻止集.改进Needleman—Wunsch算法中动态规划矩阵的递归计算方法,增加超前比较和插入非空占位符的思想,在相同空间复杂度和时间复杂度下采用回溯路径矩阵来加快回溯过程,并辨别回溯方向.采用三种类型的地质剖面图数据对系统进行对比测试,实验结果表明,基于改进的序列比对算法的地层对比连层结果要优于理正勘察CAD系统和美国GAEA Technologies公司的WinFence系统.