Automata-theoretic models of mutation and alignment.
Finite-state automata called transducers, which have both input and output, can be used to model simple mechanisms of biological mutation. We present a methodology whereby numerically-weighted versions of such specifications can be mechanically adapted to create string edit machines that are essentially equivalent to recurrence relations of the sort that characterize dynamic programming alignment algorithms. Based on this, we have developed a visual programming system for designing new alignment algorithms in a rapid-prototyping fashion.
Searls
D B
DB
Department of Genetics University of Pennsylvania School of Medicine, Philadelphia 19104-6145, USA.
Murphy
K P
KP
D000465:Algorithms; D001331:Automation; D001483:Base Sequence; D004276:DNA, Satellite / Q000235:genetics; D016368:Frameshift Mutation; D008390:Markov Chains; D008957:Models, Genetic; D008969:Molecular Sequence Data; D009154:Mutation; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D017384:Sequence Deletion; D012984:Software
D004276:DNA, Satellite; D011506:Proteins