Motif Finding Using Non-Deterministic Finite Automata
Date
2015-11-15
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and Engineering, Islamic University of Technology, Gazipur, Bangladesh
Abstract
Motif Finding is one of the topmost concerns on the basis of characteristics
of the species and its primary concept is finding the common DNA sequence
that specifies a certain characteristics of a species. In this thesis, here we
propose a methodology of finding method using an algorithm called nondeterministic
finite automata. Our primary concern is finding the best
common sequence that follows the pattern and gives an accurate result with
minimization of errors. And following that solving complexity issue that
occurs in automaton system, we try to minimize the system time and space
complexity so that it can find pattern with less storage needed. Using nondeterministic
approach so far we provided a better solution approach with
patterns both in matched and gapped situation.
Description
Supervised by
Tareque Mohmud Chowdhury
Assistant Professor
Department of Computer Science and Engineering(CSE)
Islamic University of Technology (IUT)
Keywords
Citation
[1] Yazmín Magallanes, Ivan Olmos : Motifs Recognition in DNA Sequences Comparing the Motif Finding Automaton Algorithm against a Traditional Approach, Universidad de las Américas, Puebla, 2010 [2] Pavlos Antoniou, Jan Holub : Finding Common Motifs with Gaps using Finite Automata, Dept. of Computer Science, King's College London, London, 2006 [3] Tobias Marschall: Construction of minimal DFAs from biological motifs, Bioinformatics for High-Throughput Technologies, Computer Science XI, Dortmund, Germany, December 9, 2010 [4] Grégory Nuel: Significance Score of Motifs in Biological Sequences, Institute for Mathematical Sciences (INSMI), CNRS, Paris, November 2, 2011 [5] Markus Holzer: Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity, Institut für Informatik Gießen, Hesse, Germany, January 2008 [6] Christopher Sabotta: Advantages and challenges of programming the Micron Automata Processor, Iowa State University, 2013 [7] Tobias Marschall: Algorithms and Statistical Methods for Exact Motif Discovery, Bioinformatics for High-Throughput Technologies, Computer Science XI, Dortmund, Germany, 2014 [8] Indranil Roy and Srinivas Aluru: Finding Motifs in Biological Sequences using the Micron Automata Processor, School of Computational Science and Engineering Georgia Institute of Technology, Atlanta, GA 30332, 2014 [9] L’ubomíra Išto ˇnová: Descriptional Complexity of Finite State Automata , Pavol Jozef Šafárik University in Košice, September 9, 2010 [10] Kayleigh Hyde: NONDETERMINISTIC FINITE STATE COMPLEXITY, University of Hawai’i, Manoa, April 2013 [11] Adnan Ferdous Ashrafi , A.K.M Iqtidar Newaz :A Modified Algorithm For DNA Motif Finding Considering Mutation, Department of Computer Science and Engineering (CSE) Islamic University Of Technology(IUT), 2014 30 [12] Sabine Broda, Ant_onio Machiavelo: Average Case Complexity of NFA's, Centro de Matem_atica da Universidade do Porto, 2008 [13] Nadia Pisanti_z, Alexandra M. Carvalho: RISOTTO: Fast extraction of motifs with mismatches, Dipartimento di Informatica, Universit_a di Pisa, Italy ,2002 [14] Paolo Ribeca∗ and Emanuele Raineri: Faster exact Markovian probability functions for motif occurrences: a DFA-only approach, Bioinformatics and Genomics Unit, Center for Genomic Regulation, C/ Dr.Aiguader 88, E08003 Barcelona, Spain, page 2839-2848, October 9, 2008 [15] Maxime Crochemore and Christophe Hancart. Automata for matching patterns. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume2, Linear Modeling: Background and Application, chapter 9, pages 399–462. SpringerVerlag, 1997.