Given a string s on an alphabet Sigma, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem axe polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases.

Flipping Letters to minimize the Support of a String.

RIZZI, ROMEO
2008

Abstract

Given a string s on an alphabet Sigma, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem axe polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases.
De Bruijn graphs; codons; string algorithms; parametrized complexity; k-mers
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/409546
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact