INCIDENCE MATRICES AND INTERVAL GRAPHS
RAND PROJECT AIR FORCE ARLINGTON VA
Pagination or Media Count:
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 1s in each colum 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.
- Numerical Mathematics