0
$\begingroup$

We have a column which has following format : (1, 1, 1, 0, 1).

Here is the definition of what means two columns are compatible.

Using the notation Oi to denote the collection of rows possessing a 1 in their i-th element, we conclude that one of three possibilities must be true: Oi ⊆ Oj , Oj ⊆ Oi , or Oi and Oj are disjoint (the first two cases include the possibility that Oi = Oj). If columns i and j satisfy this condition, then we call them compatible

The question is : How many possible columns of length 5 are compatible with the column (1, 1, 1, 0, 1)?

You can read more here where problem is described in page 14-16.

Thanks in advance !

$\endgroup$
4
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it is not a question about bioinformatics. $\endgroup$ Commented Jan 9, 2018 at 9:11
  • $\begingroup$ @AlexReynolds, I attached a link and you will see that is about bioinformatics. $\endgroup$ Commented Jan 9, 2018 at 9:13
  • $\begingroup$ In the document there are also algorithms for finding genes tree. $\endgroup$ Commented Jan 9, 2018 at 9:14
  • 2
    $\begingroup$ That the topic it can be applied is in bioinformatics doesn't make your question about bioinformatics. You can edit explaining what is 1 and 0 and which is your bioinformatic question. But it seems a nice problem $\endgroup$
    – llrs
    Commented Jan 9, 2018 at 11:13

1 Answer 1

2
$\begingroup$

Let $n$ be the number of rows (in your case $n=5$) and $|O_j|$ the cardinality of $O_i$.

We can calculate the number of compatible columns as sum of the number of $O_i \subseteq O_j$, $O_j \subseteq O_i$ and $O_i, O_j$ disjoint.

number of $O_i \subseteq O_j$: Here we need to find the number of supersets of our $O_i$. That means we need to find the number of sets which contain the indices in $O_i$ and for each index not in $O_i$, we have two choices: It is contained, or it is not contained in $O_j$. Therefore the number of supersets is $2^{n-|O_i|}$, which is 2 to the power of elements not in our set.

number of $O_i, O_j$ disjoint: Here all elements of $O_i$ are fixed not to be in $O_j$ and for each index not in $O_i$, it can again be in $O_j$ or not. That means that the number of possible sets is again $2^{n-|O_i|}$.

number of $O_j \subseteq O_i$: Here we need to find the number of subsets of $O_i$ and this is the number of elements in its power set, which is $2^{|O_i|}$.

So finally, this means that the number of compatible columns can be calculated as: $2^{n-|O_i|} + 2^{n-|O_i|} + 2^{|O_i|} - 2$.

Why -2? We have counted 2 sets twice:

  • The empty set, which is a subset of $O_i$ and also counted in the number of disjoint sets
  • and $O_i$, which we counted in $O_i \subseteq O_j$ and in $O_j \subseteq O_i$

This means for your examle, we have $16 + 2 + 2 - 2 = 18$ compatible sets.

Note: The all zero vector (which corresponds to $O_i=\{\}$) is a special case for which the formula above does not work, as all disjunct sets and all supersets are counted twice. For this special case, the number of compatible columns is simply $2^n$.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer. How do you calculate |Oi| ? $\endgroup$ Commented Jan 9, 2018 at 10:24
  • $\begingroup$ $|O_i|$ is the number of elements in $O_i$, so for your column $|O_i|$ is 4 because $O_i = \{1,2,3,5\}$ $\endgroup$
    – Bluescreen
    Commented Jan 9, 2018 at 10:26
  • $\begingroup$ In my example why is not 5 ? Cardinal({1,1,1,0,1})=5 $\endgroup$ Commented Jan 9, 2018 at 10:30
  • $\begingroup$ The cardinality of your column is 5. But in your definition: "Using the notation Oi to denote the collection of rows possessing a 1 in their i-th element,", $O_i$ is the set of rows with a 1. In your column there are 4 rows with a one, so the cardinality of $O_i$ = 4 $\endgroup$
    – Bluescreen
    Commented Jan 9, 2018 at 10:32
  • $\begingroup$ Thanks a lot for your explanation.Now I understand. It means that for (0,0,0,0,0) the answer is 2^5+2^5+2^0-2 =63 ? $\endgroup$ Commented Jan 9, 2018 at 10:33

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