A Heuristic Algorithm for Optimal Alignment and Matching of Borehole Stratigraphy

This paper presents an heuristic algorithm, Auto-Align Boreholes (AAB), that computes near-optimal stratigraphy sequences from borehole horizons to define subsurface geology in a computationally efficient manner. Matching horizons across boreholes is not trivial and problem complexity grows exponentially with the number of horizons and boreholes. Our algorithm is based on the Smith and Watermen algorithm used in gene sequencing with modifications. Our algorithm computes a near optimal alignment between the horizons, subject to constraints. Matching horizons to develop subsurface models has traditionally been done manually, but for large sets of boreholes, manually selecting the horizons becomes difficult. Other methods exist to compute optimal sequences but they become computationally infeasible for even moderate numbers of boreholes. The optimal alignment problem can be solved exactly by a multiple sequence alignment distance matrix (an exhaustive search method) but is computationally infeasible for even moderate-sized borehole sets. The literature presents other approaches such as dendrographic algorithms and genetic algorithms. Dendrographic method computational requirements vary with the number of borehole pairs squared (or cubed) and the results depend on the order in which sequences are paired. Genetic algorithms must be run many times to ensure that the solution found is not a local minimum (of which there many) and requires a long runtime if the number of boreholes is relatively large. The AAB algorithm was implemented in the Groundwater Modeling System (GMS), a subsurface pre- and post processing system developed by the United States Army Corps of Engineers. The GMS system can compute and present the borehole horizon information to generate subsurface stratigraphic models.