tailieunhanh - Báo cáo sinh học: "The approximability of the String Barcoding problem"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: The approximability of the String Barcoding problem. | Algorithms for Molecular Biology BioMed Central Research Open Access The approximability of the String Barcoding problem Giuseppe Lancia and Romeo Rizzi Address Dipartimento di Matematica ed Informatica Universitá di Udine Via delle Scienze 206 Udine Italy Email Giuseppe Lancia - lancia@ Romeo Rizzi - rizzi@ Corresponding author Received 16 May 2006 Accepted 08 August 2006 Published 08 August 2006 Algorithms for Molecular Biology 2006 1 12 doi 1748-7188-1-12 This article is available from http content 1 1 12 2006 Lancia and Rizzi licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License http licenses by which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. Abstract The String Barcoding SBC problem introduced by Rash and Gusfield RECOMB 2002 consists in finding a minimum set of substrings that can be used to distinguish between all members of a set of given strings. In a computational biology context the given strings represent a set of known viruses while the substrings can be used as probes for an hybridization experiment via microarray. Eventually one aims at the classification of new strings unknown viruses through the result of the hybridization experiment. In this paper we show that SBC is as hard to approximate as Set Cover. Furthermore we show that the constrained version of SBC with probes of bounded length is also hard to approximate. These negative results are tight. Background The following setting was introduced by Rash and Gus-field in 1 Given a set Vof n strings v1 . vn representing the genomes of n known viruses and an extra string s representing a virus in V but not yet classified we aim at recognizing s as one of the known viruses through an hybridization experiment. In the experiment we utilize a set n of k probes DNA strings and we will