I am interested in the following problem. One has two collections $Q$ and $T$ of strings, and a set $A$ of alignments of strings in $Q$ to strings in $T$. I want to find a subset $A'$ of $A$ that (i) involves each element of $Q$ only once and (ii) maximizes the total number of characters in elements $T$ that are covered by an alignment in $A'$.

(To be precise: Let $a$ be an alignment in $A$. We can think of $a$ as a tuple $(q,t,f)$ where $q\in Q$, $t\in T$, and $f : \mathcal I_a \to \mathcal J_a$ is a bijection such that $f(i)=j$ if $a$ aligns the $i$th character of $q$ to the $j$th character of $t$. Here $\mathcal I_a \subset \{1,2,\dots,|q|\}$ and $\mathcal J_a \subset \{1,2,\dots,|t|\}$, where $|\cdot|$ means length. We can think of characters in elements of $T$ as pairs $(t,j)$ where $t\in T$ and $j\in\{1,2,\dots,|t|\}$. We say that $(t,j)$ is covered by an alignment in $A'$ if there exists $a=(q,t',f)\in A'$ such that $t=t'$ and $j\in\mathcal J_a$. (Note that there might exist several such $a\in A'$.) Let $\chi(t,j,A') = 1$ if such an $a\in A'$ exists, and 0 otherwise. We want to maximize the cardinality of $\{(t,j) : \chi(t,j,A')=1\}$ over $A'\subset A$ such that for all $q\in Q$, there exists at most one $a=(q',t,f)\in A'$ with $q=q'$.)

My question: What is a name for this problem, if any? Thanks in advance! I guess that it is related to maximum matchings and maximum coverage, but it's not quite the same as either.

  • 1
    $\begingroup$ This sounds really close to the set cover problem. en.wikipedia.org/wiki/Set_cover_problem $\endgroup$ – Joshua Herman May 22 '12 at 4:16
  • $\begingroup$ @Joshua Herman. Thanks. A big difference, though, unless I'm missing something, is that we don't require that all the characters in elements of T are covered; rather, we want to maximize the number of covered elements. $\endgroup$ – N F May 22 '12 at 13:22
  • $\begingroup$ (The end of my previous comment should be: "rather, we want to maximize the number of covered characters.") $\endgroup$ – N F May 22 '12 at 13:33
  • 1
    $\begingroup$ Ok then it is the maximum cover problem. en.wikipedia.org/wiki/Maximum_coverage_problem $\endgroup$ – Joshua Herman May 22 '12 at 16:07

This sounds like the maximum cover problem which is NP-hard.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.