In my work I have several datasets of so-called SNP chips. They have for several individuals (1-3) and DNA positions ("Markers") the "letter" which is found at that position.
The problem with this data is that before merging them, I need to invert the data from some chips. The reason is that you can always specify the "letter" at a DNA position in two ways, because each letter has its complement letter (A <-> T, G <-> C) present on the opposite DNA strand. My data does not tell me from which strand each chip has the letter, so I need to infer that.
My individuals are measured on multiple, but not all chips. So I can infer whether two chips are in an inverse relationship or not by looking at the same individual on both chips. I expect the same letter. If I find the complement letter, I know these two chips are in an inverse relationship. The problem is to find out which chips to invert to satisfy all the relationships between the chips. I have a working solution but only in "lab-conditions", so only if I have no errors in my data.
Question: How is this kind of problem called in informatics and is there an error-tolerant algorithm to solve it?
Below, I have an example, and the exact solution that I have come up with so far.
This is the example dataset, we only need to care about one marker (M1) and three individuals (1-3):
Chip1: | Chip2: | Chip3:
M1 | M1 | M1
1 A | 2 C | 1 A
2 G | 3 C | 3 G
We see that individual 2 has a G on chip 1 but a C on chip 2. Therefore, chip 2 gives me data from the opposite strand of the strand of chip 1. Therefore, we need to invert the letters on either chip 1 or chip 2 to homogenize the data.
Similarly, we need to invert either chip 2 or chip 3 because for individual 3 we see inverted data on the two chips.
To complete the picture, chip 1 and chip 3 do not need to be inverted with respect to each other, because the letter for individual 1 is A on both chips.
Solution: Either invert chip 2 or to invert both chip 1 and chip 3 to make all letters match.
Approach 1: Graph
We can formulate the problem as a graph with two kinds of edges and two kinds of vertices. We need to find out types of the vertices. We know which edge has which type, we have "straight" edges that connect vertices of the same kind and "inverted" edges that connect vertices of opposite kind:
Approach 2: System of equations
We can write the problem as a system of equations:
1. A = -B
2. A = C
3. B = -C
equals to:
1. A + B = 0
2. A - C = 0
3. B + C = 0
which can be written in matrix form
( 1 1 0 ) (A) (0)
| 1 0 -1 | * |B| = |0|
( 0 1 1 ) (C) (0)
This answer on Math SE tells me I can solve this if I determine the null space of my matrix, which I can do in R:
M = rbind(
c(1, 1, 0),
c(1, 0, -1),
c(0, 1, 1)
)
round(MASS::Null(t(M)),4) # right null space: find x so that Mx = 0
## [,1]
## [1,] 0.5774
## [2,] -0.5774
## [3,] 0.5774
This is a solution that corresponds to one of the two solutions shown above: Invert B and do not invert A and C.
Also works for a case of 4 chips, where I need to invert two of them:
M = rbind(
c(1, -1, 0, 0),
c(1, 0, 1, 0),
c(1, 0, 0, 1),
c(0, 1, 1, 0),
c(0, 1, 0, 1),
c(0, 0, 1, -1)
)
MASS::Null(t(M))
## -0.5 -0.5 0.5 0.5
The problem is that this does not tell me which chip to discard if I have conflicting information (because SNP calls might have errors in practice). Flipping the sign of one number gives me an empty output
M = rbind(
c(1, +1, 0, 0), # <<- error here!
c(1, 0, 1, 0),
c(1, 0, 0, 1),
c(0, 1, 1, 0),
c(0, 1, 0, 1),
c(0, 0, 1, -1)
)
MASS::Null(t(M))
##
## [1,]
## [2,]
## [3,]
## [4,]
Is there a way to find out which relationships cause the problem?