The week's pick
Random Articles
Reseach Article
The Weighted Factors Automaton : A Tool for DNA Sequences Analysis
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 70 - Number 4 |
| Year of Publication: 2013 |
| Authors: Christiane Hespel, Farida Benmakrouha, Danielle Quichaud |
10.5120/11947-7763
|
Christiane Hespel, Farida Benmakrouha, Danielle Quichaud . The Weighted Factors Automaton : A Tool for DNA Sequences Analysis. International Journal of Computer Applications. 70, 4 ( May 2013), 1-7. DOI=10.5120/11947-7763
Abstract
A lot of computing tools are often used for analyzing DNA sequences like trees, automata, dictionaries, every one being reserved for a particular problem. A. Blumer and al. have proposed a more general computing tool : the smaller automaton recognizing the subwords of a text (DAWG). In this paper we propose the concept of "weighted factors automaton" producing every occurrence of any factor. Its transitions are labeled by the read letter and weighted by the set of the indices of the factors beginnings. The factors are obtained by concatenating the read letters and the indices of the factors beginnings are obtained by computing the intersection of the weighting sets, when advancing from the initial state to a final state. We think that this automaton can be more easily processed than DAWG and we present a comparison between DAWG and our automaton: the set of the factors beginnings indices and the factors frequency are more easily obtained by our automaton and the restriction of our automaton to the factors of length k maintains the automaton structure, when DAWG cannot be easily restricted. The applications are numerous: By selecting factors of length 1, we obtain the coding regions, factors of length 3, we obtain the expression level of some gene. The "weighted factors automaton" allows us to find matches of pattern, to study homology, FASTA and BLAST algorithms being significantly simplified
References
- J. BERSTEL, C. REUTENAUER, Rational series and their languages. Springer-Verlag, 1988.
- A. BLUMER, J. BLUMER, D. HAUSSLER, A. EHRENFEUCHT, M. T. CHEN, J. DEIFERAS, The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 1985, 31–35.
- M. CROCHEMORE, Transducers and repetitions. Theor. Comput. Sci. 45, 1986, 63–86.
- M. CROCHEMORE, C. HANCART, T. LECROQ, Algorithms on strings. Cambridge University Press, 2007.
- F. DARDEL, F. K´EP`E S, Bioinformatique, G´enomique et post-g´enomique. Editions de l'Ecole Polytechnique, 2002.
- S. FARO, T. LECROQ, A Fast Suffix Automata Based Algorithm for Exact Online String Matching. LNCS 7276, Springer-Verlag, to appear, 149–158.
- P. FLAJOLET, R. SEDGEWICK, Introduction `a l'analyse des algorithmes. International Thomson Publishing, 1998.
- M. FLIESS, Un outil alg´ebrique : les s´eries formelles non commutatives. In: G. MARCHESINI, S. K. MITTER (ed. ), Mathematical System Theory. LNEMS 131, Springer-Verlag, 1976, 122–148.
- D. GUSFIELD, Algorithms on Strings, Trees and Sequences. Cambridge University Press, 1997.
- D. L. HARTL, E. W. JONES, G´en´etique, Les grands principes. Dunod, 2003.
- C. HESPEL, Une ´etude des s´eries formelles non commutatives pour l'Approximation et l'Identification des syst`emes dynamiques. Th`ese d'´etat, Univ. of Lille 1, 1998.
- C. N. JONES, A. P. PEVZNER, An introduction to Bioinformatics Algorithms. MIT Press, 2004.
- A. LEFEBVRE, T. LECROQ, H. DAUCHEL, J. ALEXANDRE, FORRepeats Bioinformatics (2003).
Index Terms
Keywords