According to present genetic
theory, the fine structure of genes consists of linearly ordered elements. A mutant
gene is obtained by alteration of some connected portion of this structure. By
examining data obtained from suitable experiments, it can be determined whether or
not the blemished portions of two mutant genes intersect or not, and thus
intersection data for a large number of mutants can be represented as an undirected
graph. If this graph is an “interval graph,” then the observed data is consistent with a
linear model of the gene.
The problem of determining when a graph is an interval graph is a special case of
the following problem concerning (0,1)-matrices: When can the rows of such a matrix
be permuted so as to make the 1’s in each column appear consecutively? A complete
theory is obtained for this latter problem, culminating in a decomposition theorem
which leads to a rapid algorithm for deciding the question, and for constructing the
desired permutation when one exists.
