Edit metric decoding: Return of the side effect machines

Abstract

Side Effect Machines (SEMs) are an extension of finite state machines which place a counter on each node that is incremented when that node is visited. Previous studies examined a genetic algorithm to discover node connections in SEMs for edit metric decoding for biological applications, namely to handle sequencing errors. Edit metric codes, while useful for decoding such biologically created errors, have a structure which significantly differentiates them from other codes based on Hamming distance. Further, the inclusion of biologically- motivated restrictions on allowed words makes development of decoders a bespoke process based on the exact code used. This study examines the use of evolutionary programming for the creation of such decoders, thus allowing for the number of states to be evolved directly, not witnessed in previous approaches which used genetic algorithms. Both direct and fuzzy decoding are used, obtaining correct decoding rates of up to 95% in some SEMs.