Parameterized lower bound and inapproximability of polylogarithmic string barcoding

Chunmei Liu (), Yinglei Song () and Legand L. Burge ()
Additional contact information
Chunmei Liu: Howard University
Yinglei Song: University of Maryland Eastern Shore
Legand L. Burge: Howard University

Journal of Combinatorial Optimization, 2008, vol. 16, issue 1, No 4, 39-49

Abstract: Abstract String barcoding is a method that can identify microorganisms by analyzing their genome sequences. In this paper, we study the polylogarithmic string barcoding problem, where the lengths of the substrings in the testing set are polylogarithmically bounded. In particular, we show that the polylogarithmic string barcoding problem remains NP-hard and moreover, for a problem instance with n sequences, it is NP-hard to achieve an approximate ratio within dln n in polynomial time, where d is some constant. We then consider the parameterized polylogarithmic string barcoding problem, where the number of substrings in the test set is considered to be a fixed parameter k. We show that, unless W[2]=FPT, there does not exist a 2 O(k) n c algorithm that can decide whether a test set of size k exists or not, where c is a constant independent of n and k.

Keywords: Polylogarithmic string barcoding; Inapproximability; Parameterized lower bound (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9097-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:16:y:2008:i:1:d:10.1007_s10878-007-9097-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9097-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().