Embedding on alphabet overlap digraphs

摘要

Alphabet overlap digraphs can be viewed as a generalization of directed de Bruijn graphs. Given three integers α ≥ 1, k ≥ 2 and 1 ≤ i < k, the alphabet overlap digraph O(α, k ; i) is a digraph: the set of all words of length k over a certain alphabet with cardinality α is vertex set, and there is an arc from a vertex u to a vertex v if and only if the word of last k−i letters of u coincides with the word of first k−i letters of v. In this paper, we consider whether O(α, k ; i) can be embedded in O(α, k ; j) for given integers 1 ≤ i < j < k. In order to resolve this problem, we give an O(1)-time algorithm to decide whether there exists a permutation on {1, . . . ,k} from O(α, k ; i) to O(α, k ; j). If such a permutation exists, for any vertex of O(α, k ; i), we apply the permutation to change its label’s position and map it to a vertex of O(α, k ; j). Furthermore, we obtain an embedding from O(α, k ; i) to O(α, k ; j). Hence, we solve partly the problem. As a consequence, we show that every directed de Bruijn graph can be embedded in all alphabet overlap digraphs with the same parameters α and k. Keywords DNA graph - Directed de Bruijn graphs - Alphabet overlap digraphs - Embedding