Choose a set of markers to distinguish individuals

user_14633866 0
Viewed 39

I have some genotype data from 8 markers and 20 individuals. I would like to select 5 markers from the 8 markers, which can form a unique genotype pattern for each individual. The purpose is to select as few as possible markers to distinguish the 20 individuals.

I know that I need to select 5 columns out of 8, and then compare each row. If we find duplicated rows, then we need to re-select another 5 columns, until we find no duplicated rows.

But I don't know how I can translate it into R. Could somebody help? Thanks!

sample data

Indiv   MN1 MN2 MN3 MN4 MN5 MN6 MN7 MN8
1   A   C   C   A   C   G   A   T
2   A   C   T   A   T   A   A   T
3   A   C   T   G   C   A   A   C
4   A   C   T   G   C   G   G   C
5   A   T   C   G   C   A   A   C
6   A   T   C   G   C   A   G   C
7   A   T   T   A   T   A   A   T
8   A   T   T   A   T   A   G   T
9   A   T   T   A   T   G   G   C
10  G   C   C   A   C   A   A   C
11  G   C   C   A   C   G   A   T
12  G   C   C   G   C   G   G   T
13  G   C   C   G   T   G   G   T
14  G   C   T   G   C   G   A   T
15  G   C   T   G   T   A   G   C
16  G   T   C   A   T   A   G   T
17  G   T   C   G   T   A   A   C
18  G   T   T   A   C   G   G   T
19  G   T   T   G   T   G   G   T
sampling r
1 Answers

Impossible. Assume that we can't change the order of markers. You need at least 6 markers to distinguish the individuals. Consider this function (brute-force solution).

distinct_combn <- function(df, m) {
  out <- combn(df, m, function(x) {
    if (nrow(unique(x)) == nrow(x)) names(x) else character(0L)
  }, simplify = FALSE)
  out[lengths(out) > 0L]
}

Then we can see that

> distinct_combn(df[, -1L], 5)
list()

> distinct_combn(df[, -1L], 6)
[[1]]
[1] "MN1" "MN2" "MN3" "MN5" "MN6" "MN7"

[[2]]
[1] "MN1" "MN2" "MN3" "MN5" "MN7" "MN8"

[[3]]
[1] "MN1" "MN2" "MN4" "MN5" "MN6" "MN7"

[[4]]
[1] "MN1" "MN2" "MN4" "MN5" "MN7" "MN8"

Data I used

> df
   Indiv MN1 MN2 MN3 MN4 MN5 MN6 MN7 MN8
1      1   A   C   C   A   C   G   A   T
2      2   A   C   T   A   T   A   A   T
3      3   A   C   T   G   C   A   A   C
4      4   A   C   T   G   C   G   G   C
5      5   A   T   C   G   C   A   A   C
6      6   A   T   C   G   C   A   G   C
7      7   A   T   T   A   T   A   A   T
8      8   A   T   T   A   T   A   G   T
9      9   A   T   T   A   T   G   G   C
10    10   G   C   C   A   C   A   A   C
11    11   G   C   C   A   C   G   A   T
12    12   G   C   C   G   C   G   G   T
13    13   G   C   C   G   T   G   G   T
14    14   G   C   T   G   C   G   A   T
15    15   G   C   T   G   T   A   G   C
16    16   G   T   C   A   T   A   G   T
17    17   G   T   C   G   T   A   A   C
18    18   G   T   T   A   C   G   G   T
19    19   G   T   T   G   T   G   G   T

> dput(df)
structure(list(Indiv = 1:19, MN1 = c("A", "A", "A", "A", "A", 
"A", "A", "A", "A", "G", "G", "G", "G", "G", "G", "G", "G", "G", 
"G"), MN2 = c("C", "C", "C", "C", "T", "T", "T", "T", "T", "C", 
"C", "C", "C", "C", "C", "T", "T", "T", "T"), MN3 = c("C", "T", 
"T", "T", "C", "C", "T", "T", "T", "C", "C", "C", "C", "T", "T", 
"C", "C", "T", "T"), MN4 = c("A", "A", "G", "G", "G", "G", "A", 
"A", "A", "A", "A", "G", "G", "G", "G", "A", "G", "A", "G"), 
    MN5 = c("C", "T", "C", "C", "C", "C", "T", "T", "T", "C", 
    "C", "C", "T", "C", "T", "T", "T", "C", "T"), MN6 = c("G", 
    "A", "A", "G", "A", "A", "A", "A", "G", "A", "G", "G", "G", 
    "G", "A", "A", "A", "G", "G"), MN7 = c("A", "A", "A", "G", 
    "A", "G", "A", "G", "G", "A", "A", "G", "G", "A", "G", "G", 
    "A", "G", "G"), MN8 = c("T", "T", "C", "C", "C", "C", "T", 
    "T", "C", "C", "T", "T", "T", "T", "C", "T", "C", "T", "T"
    )), class = "data.frame", row.names = c(NA, -19L))
user_108024990
Related