Closest string with outliers
2011

Finding Common Patterns in Strings with Outliers

publication Evidence: moderate

Author Information

Author(s): Christina Boucher, Bin Ma

Primary Institution: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON

Hypothesis

Can we find a center string that is close to most input strings while ignoring outliers?

Conclusion

The proposed model effectively identifies a center string that represents a majority of input strings while revealing outliers.

Supporting Evidence

  • The CLOSEST STRING problem is NP-complete, indicating the difficulty of finding a solution.
  • The CSWO model allows for a more flexible approach by accommodating outliers.
  • Algorithms for CSWO are provided for both bounded and unbounded alphabets.

Takeaway

This study helps us find a string that is similar to most others, even if some are very different. It's like finding a common favorite toy among a group of kids, even if one kid has a completely different toy.

Methodology

The study introduces a refined model called the CLOSEST STRING WITH OUTLIERS (CSWO) and provides algorithms for solving it.

Limitations

The model's effectiveness can be sensitive to the choice of parameters and the presence of outliers.

Digital Object Identifier (DOI)

10.1186/1471-2105-12-S1-S55

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication