| DEALING WITH HARDWARE SPACE LIMITS WHEN REMOVING EPSILON-TRANSITIONS IN A GENOMIC WEIGHTED FINITE AUTOMATON (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| ABSTRACT Weighted Finite Automata (WFA) over (max; +)-semirings are used for pattern matching in genomic databanks with substitution costs. They can be efficiently parsed using reconfigurable hardware like FPGAs (Field Programmable Gate Arrays) implementing the linear encoding scheme. In biological applications, one wants to double every regular transition with an "-transition to modelize deletions. Critical paths in the FPGA prevent chains of "-transitions from being arbitrarily large, so the "-transitions must be removed. Generic "-transitions-removal algorithms produce too many new transitions. We propose an analysis of the "-transitions-removal under a condition of path-equivalence. In particular, we give a constructive way to remove the "-transitions on the linear-shaped parts of a WFA and an optimal bound of the number of new transitions produced. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||