Automata-theoretic models of mutation and alignment

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Design

Background:

• Finite-state transducers are computational models with input and output capabilities.
• These models can represent simple biological mutation processes.
• Existing alignment algorithms often rely on dynamic programming and recurrence relations.

Purpose of the Study:

• To develop a methodology for adapting finite-state transducers into string edit machines.
• To create a system for rapid prototyping of new sequence alignment algorithms.
• To bridge the gap between mutation modeling and algorithmic design in bioinformatics.

Main Methods:

• Utilizing numerically-weighted finite-state transducers.
• Mechanically adapting transducer specifications into string edit machines.
• Developing a visual programming system for algorithm design.

Main Results:

• String edit machines equivalent to dynamic programming recurrence relations were created.
• A functional visual programming system for rapid algorithm prototyping was developed.
• The methodology facilitates the design of novel alignment algorithms.

Conclusions:

• Finite-state transducers provide a viable framework for developing sequence alignment algorithms.
• The visual programming system accelerates the design and testing of bioinformatics tools.
• This approach offers a novel perspective on modeling biological mutations and sequence analysis.