On the closest string via rank distance

Liviu P. Dinu, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

Given a set S of k strings of maximum length n, the goal of the closest substring problem (CSSP) is to find the smallest integer d (and a corresponding string t of length ℓ ≤ n) such that each string s ∈ S has a substring of length ℓ of "distance" at most d to t. The closest string problem (CSP) is a special case of CSSP where ℓ = n. CSP and CSSP arise in many applications in bioinformatics and are extensively studied in the context of Hamming and edit distance. In this paper we consider a recently introduced distance measure, namely the rank distance. First, we show that the CSP and CSSP via rank distance are NP-hard. Then, we present a polynomial time k-approximation algorithm for the CSP problem. Finally, we give a parametrized algorithm for the CSP (the parameter is the number of input strings) if the alphabet is binary and each string has the same number of 0's and 1's.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings
Pages413-426
Number of pages14
DOIs
Publication statusPublished - Jul 4 2012
Event23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012 - Helsinki, Finland
Duration: Jul 3 2012Jul 5 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7354 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012
CountryFinland
CityHelsinki
Period7/3/127/5/12

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Dinu, L. P., & Popa, A. (2012). On the closest string via rank distance. In Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings (pp. 413-426). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7354 LNCS). https://doi.org/10.1007/978-3-642-31265-6_33