Title :
Side effect machines for quaternary edit metric decoding
Author :
Brown, Joseph Alexander ; Houghten, Sheridan K. ; Ashlock, Daniel
Author_Institution :
Sch. of Comput. Sci., Univ. of Guelph, Guelph, ON, Canada
Abstract :
DNA edit metric codes are used as labels to track the origin of sequence data. This study is the first to treat sophisticated decoders for these error-correcting codes. Side effect machines can provide efficient decoding algorithms for such codes. Two methods for automatically producing decoding algorithms are presented. Side Effect Machines (SEMs), generalizations of finite state automata, are used in both. Single Classifier Machines (SCMs) use a single side effect machine to classify all words within a code. Locking Side Effect Machines (LSEMs) use multiple side effect machines to create a tree structured iterated classification. This study examines these techniques and provides new decoders for existing codes. Presented are ideas for best practises for the creation of these two types of new edit metric decoders. Codes of the form (n,M,d)4 are used in testing due to their suitability for bioinformatics problems. A group of (12, 54-56, 7)4 codes are used as an example of the process.
Keywords :
bioinformatics; error correction codes; finite state machines; iterative methods; pattern classification; trees (mathematics); DNA edit metric codes; bioinformatics problems; error-correcting codes; finite state automata; locking side effect machines; multiple side effect machines; quaternary edit metric decoding; single classifier machines; tree structured iterated classification; Automata; Bioinformatics; Biological information theory; Classification tree analysis; DNA; Error correction; Error correction codes; Iterative decoding; Organisms; Sequences; Bioinformatics; Genetic algorithms;
Conference_Titel :
Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), 2010 IEEE Symposium on
Conference_Location :
Montreal, QC
Print_ISBN :
978-1-4244-6766-2
DOI :
10.1109/CIBCB.2010.5510422
