title: Reconstruction of DNA sequences using genetic algorithms and cellular automata: towards mutation prediction?
abstract: Change of DNA sequence that fuels evolution is, to a certain extent, a deterministic process because mutagenesis does not occur in an absolutely random manner. So far, it has not been possible to decipher the rules that govern DNA sequence evolution due to the extreme complexity of the entire process. In our attempt to approach this issue we focus solely on the mechanisms of mutagenesis and deliberately disregard the role of natural selection. Hence, in this analysis, evolution refers to the accumulation of genetic alterations that originate from mutations and are transmitted through generations without being subjected to natural selection. We have developed a software tool that allows modelling of a DNA sequence as a one-dimensional cellular automaton (CA) with four states per cell which correspond to the four DNA bases, i.e. A, C, T and G. The four states are represented by numbers of the quaternary number system. Moreover, we have developed genetic algorithms (GAs) in order to determine the rules of CA evolution that simulate the DNA evolution process. Linear evolution rules were considered and square matrices were used to represent them. If DNA sequences of different evolution steps are available, our approach allows the determination of the underlying evolution rule(s). Conversely, once the evolution rules are deciphered, our tool may reconstruct the DNA sequence in any previous evolution step for which the exact sequence information was unknown. The developed tool may be used to test various parameters that could influence evolution. We describe a paradigm relying on the assumption that mutagenesis is governed by a near-neighbour-dependent mechanism. Based on the satisfactory performance of our system in the deliberately simplified example, we propose that our approach could offer a starting point for future attempts to understand the mechanisms that govern evolution. The developed software is open-source and has a user-friendly graphical input interface.
authors.affiliation: Democritus University of Thrace, Department of Electrical and Computer Engineering, 67100 Xanthi, Greece.
authors.forename: Ch
authors.initials: Ch
authors.lastname: Mizas
authors.forename: G Ch
authors.initials: GCh
authors.lastname: Sirakoulis
authors.forename: V
authors.initials: V
authors.lastname: Mardiris
authors.forename: I
authors.initials: I
authors.lastname: Karafyllidis
authors.forename: N
authors.initials: N
authors.lastname: Glykos
authors.forename: R
authors.initials: R
authors.lastname: Sandaltzopoulos
mesh_terms: D000465:Algorithms; D004247:DNA / Q000235:genetics*; D009154:Mutation
chemical_list: D004247:DNA