However, researchers have collected data for only about 6 percent of the possible population??“polymorphism
combinations, so most of the possible entries in the database are absent.
When population geneticists seek to find the largest possible subset of populations and polymorphisms for
which complete data exist (that is, measures exist for all polymorphisms for all populations), the researchers are
confronted by a computationally intractable problem. This problem requires that every subset of the elements
in the matrix be examined, and the number of subsets is very large!
The number of subsets among n elements is 2n, since each element can either be in a particular subset or
not. For our problem, the number of elements of our set is the number of possible entries in the database. That
is, the ALFRED database presents us with 2 (494 ??— 1600) subsets to investigate! To exhaustively test for the largest
subset with complete data, we would have to enumerate all the subsets, and test each one to see if all entries in
the subset contained measurements!
Clearly, the order of growth of such an algorithm is 2n; ??(2n). This is an exponential function of n, not
a polynomial, and it makes a very important difference.
Pages:
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71