DNA Error Correcting Codes: No Crossover
Submitted to CIBCB 2009
Daniel Ashlock,
with Sheridan K. Houghten

Abstract PDF eprint

DNA error correcting codes over the edit metric create embeddable markers for sequencing projects that are tolerant of sequencing errors. When a sequence library has multiple sources for its sequences, use of embedded markers permit tracking of sequence origin. Evolutionary algorithms are currently the best known technique for optimizing DNA error correcting codes. In this study we resolve the question of the utility of the crossover operator used in earlier studies on optimizing DNA error correcting codes. The crossover operator in question is found to be substantially counterproductive. A majority of crossover events produce results that violate minimum-distance constraints required for error correction. A new algorithm, a form of modified evolution strategy, is tested and is found to locate codes with record size. The table of best know sizes for DNA-error correcting codes is updated.