Heuristics for the De Bruijn Graph Sequence Mapping Problem

In computational biology, mapping a sequence s onto a sequence graph G is a significant challenge. One possible approach to addressing this problem is to identify a walk p in G that spells a sequence which is most similar to s . This problem is known as the Graph Sequence Mapping Problem ( GSMP ). In this paper, we study an alternative problem formulation, namely the De Bruijn Graph Sequence Mapping Problem ( BSMP ), which can be stated as follows: given a sequence s and a De Bruijn graph G k (where k ≥ 2), find a walk p in G k that spells a sequence which is most similar to s according to a distance metric. We present both exact algorithms and approximate distance heuristics for solving this problem, using edit distance as a criterion for measuring similarity.