Heuristics For The De Bruijn Graph Sequence Mapping Problem
Heuristics for the De Bruijn Graph Sequence Mapping Problem
An important problem in Computational Biology is to map a sequence s into a sequence graph G and one way to achieve this goal is to find a walk p in G such that p spells a sequence s′ most similar to s. This problem is known as Graph Sequence Mapping Problem – GSMP. In this paper we present an alternative to stating this previous problem – De Bruijn Graph Sequence Mapping Problem – BSMP which can be stated as follow: given a sequence s and a De Bruijn graph Gk, with k ≥ 2, find a walk p in Gk such that the sequence spelled by p is the most similar to s given a distance. We also present exact algorithms and approximated distance heuristics for them considering edit distance as a criterion of similarity.