Algorithmic Perspectives of the String Barcoding Problems
Sima Behpour, Bhaskar DasGupta · 2015
Applications of barcoding techniques range over a diverse range of applications such as rapid pathogen identification in epidemic outbreaks, database compression, point-of-care medical diagnosis, and monitoring of microbial communities in environmental studies. Assuming perfect hybridization, the hybridization pattern can be viewed as a string of zeros and ones, which in our terminology is the barcode of the microorganism. The barcodes corresponding to a set of microorganisms are distinct and thus the barcodes uniquely identify the organisms. This chapter discusses two specific applications of this nature. Entropy-Based Information Content Technique is based on information content (entropy) of a partial solution; the notion of information content is directly related to the Shannon information complexity. The chapter reviews few techniques from structural complexity theory that were used to prove inapproximability results for various string barcoding problems. In addition to designing efficient algorithms, one can also consider designing heuristic algorithms for barcoding problems.