On Approximating String Selection Problems with Outliers

Details On Approximating String Selection Problems with Outliers On Approximating String Selection Problems with Outliers

2012-02-13

arxiv.org/abs/1202.2820v1

Computer Science

Data Structures and Algorithms

Scientific paper

Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of same-length strings, and a parameter d, find a string x that maximizes the number of "non-outliers" within Hamming distance d of x. We prove this problem has no PTAS unless ZPP=NP, correcting a decade-old mistake. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no EPTAS unless W[1]=FPT. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult.

Affiliated with

Also associated with

No associations

Rating

On Approximating String Selection Problems with Outliers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Approximating String Selection Problems with Outliers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximating String Selection Problems with Outliers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684572