Edit metric decoding: Representation strikes back

Author

Hughes, John ; Brown, J.A. ; Houghten, Sheridan ; Ashlock, Daniel

Author_Institution

Comput. Sci., Brock Univ., St. Catharines, ON, Canada

fYear

2013

fDate

20-23 June 2013

Firstpage

229

Lastpage

236

Abstract

Quaternary error-correcting codes defined over the edit metric may be used as labels to track the origin of sequence data. When used in such applications there are typically additional restrictions that are biologically motivated, such as a required GC content or the avoidance of certain patterns. As a result such codes can not be expected to have a regular structure, making decoding particularly challenging. Previous work on decoding edit codes considered the use of side effect machines for decoding, successfully decoding up to 93.86% of error vectors. In this study the recentering/restarting algorithm is used in combination with side effect machines and an alternative representation based upon transpositions. Using the same data as in the previous work, the rate of successful decoding was significantly improved, with many cases obtaining rates very close to 100%.

Keywords

bioinformatics; GC content; edit metric decoding; quaternary error-correcting codes; recentering-restarting algorithm; sequence data; side effect machines; transposition; Biological cells; Decoding; Genetic algorithms; Sociology; Statistics; Support vector machine classification; Vectors; Bioinformatics; Evolutionary Algorithms; Representation; Sequencing;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2013 IEEE Congress on

Conference_Location

Cancun

Print_ISBN

978-1-4799-0453-2

Electronic_ISBN

978-1-4799-0452-5

Type

conf

DOI

10.1109/CEC.2013.6557575

Filename

6557575