Indexing Degenerate Strings

摘要

In this paper, we give the first, to our knowledge, structure and corresponding algorithm for indexing of factors of DNA and RNA sequences, where the text is degenerate i.e. contain sets of characters. The presented structure indexes so called k-factors, the factors of the degenerate text whose length does not exceed a given constant k. Our solution is based on the application of finite automata, the index is represented by Truncated Generalized Factor Automaton (TGFA). The size of TGFA is bounded from up by linear function of the length of text and it enables to find list occ(u) of all occurrences of for a given pattern u in degenerate text x in time ∣u∣ + ∣occ(u)∣