Search

This paper presents an algorithm for determining whether a phenotype system has a factor-union representation, i.e., whether sets of properties (factors) can be assigned to alleles so that the phenotype of each genotype is determined by the union of the factor sets of the alleles. If such a representation is possible, the algorithm can construct one using p or fewer factors, where p is the number of phenotypes. Refinements to the algorithm are presented that often construct representations using few factors. An example is presented to show that some phenotype systems can be represented only by using almost as many factors as there are phenotypes in the system. Finally, it is shown that the problem of finding factor-union representations for multilocus systems reduces to the problem for 1-locus systems.

This paper presents and explores a comprehensive mathematical model for human leukocyte antigen serology, based on a mathematical formalization of the concept of specificity. This model is general enough to take into account such factors as absorption, elution, cross-reactivity, and incomplete immunization. The paper includes a presentation of the relevant immunological background and a short discussion of the underlying computational difficulty of the basic problems. Upper and lower bounds are derived for the minimal number of specificities required to explain a given set of HLA reactions, and it is shown that the numbers of antibodies and antigens involved must be no less then this minimal number of specificities. Other techniques and theorems are also presented to aid in reducing and analyzing HLA reaction matrices.

For a complete lattice L L , in which every element is a join of completely join-irreducibles and a meet of completely meet-irreducibles (we say L L is a jm-lattice) we define the poset of irreducibles P ( L ) P(L) to be the poset (of height one) J ( L ) ∪ M ( L ) ( J ( L ) J(L) \cup M(L)(J(L) is the set of completely join-irreducibles and M ( L ) M(L) is the set of completely meet-irreducibles) ordered as follows: a > P ( L ) b a{ > _{P(L)}}b if and only if a ∈ J ( L ) , b ∈ M ( L ) a \in J(L),b \in M(L) , and a ⪇ L b a \nleqslant { _L}b . For a jm-lattice L L , the automorphism groups of L L and P ( L ) P(L) are isomorphic, L L can be reconstructed from P ( L ) P(L) , and the irreducible factorization of L L can be gotten from the components of P ( L ) P(L) . In fact, we can give a simple characterization of the center of a jm-lattice in terms of its separators (or unions of connected components of P ( L ) P(L) ). Thus P ( L ) P(L) extends many of the properties of the poset of join-irreducibles of a finite distributive lattice to the class of all jm-lattices. We characterize those posets of height 1 which are P ( L ) P(L) for some jm-lattice L L . We also characterize those posets of height 1 which are P ( L ) P(L) for a completely distributive jm-lattice, as well as those posets which are P ( L ) P(L) for some geometric lattice L L . More generally, if L L is a complete lattice, many of the above arguments apply if we use “join-spanning” and “meet-spanning” subsets of L L , instead of J ( L ) J(L) and M ( L ) M(L) . If L L is an arbitrary lattice, the same arguments apply to “join-generating” and “meet-generating” subsets of L L .

It is shown that ψ ( n ) \psi (n) , the size of the free distributive lattice on n generators (which is the number of isotone Boolean functions on subsets of an n element set), satisfies \[ ψ ( n ) ⩽ 2 ( 1 + O ( log n / n ) ) ( n [ n / 2 ] ) . \psi (n) \leqslant {2^{(1 + O(\log \;n/n))\left ( {\begin {array}{*{20}{c}} n \\ {[n/2]} \\ \end {array} } \right )}}. \] This result is an improvement by a factor n \sqrt n in the 0 term of a previous result of Kleitman. In the course of deriving the main result, we analyze thoroughly the techniques used here and earlier by Kleitman, and show that the result in this paper is “best possible” (up to constant) using these techniques.

Mathematical Immunogenetics I argued for the development of mathematics as a language for immunogenetics. A three-fold factorization of a reaction matrix was seen to be the important form of a model of a first order immunogenetic system. In the present paper, results of the authors on determining this factorization are reworked from a physical perspective and presented in an algorithmic form that can be used to compute a labeling matrix from data. Computer programs to perform these computations are in preparation.

In the predecessor to this paper, “Uncovering Antibody Incidence Structures,” Markowsky and Wohlgemuth presented a model which allowed one to calculate best possible solutions for the relation between individuals and antibodies given certain sets of tests each of which is analyzed simply for the presence or absence of a reaction. In this paper, we show that many of the concepts and theorems of the first paper generalize to the case where we actually try to compare the strengths of various reaction tests. As one might expect, the resulting model has a greater ability to detect the presence of antibodies than the model presented in the first paper. Furthermore, the additional information generated by the model described in this paper allows one to present a fairly concise definition of the best possible solution for a given amount of reaction test data.

The problem of whether it is theoretically possible to determine antigens and antibodies in a cross-reacting serological system is analyzed. Conditions are listed which will insure that the serological operations of absorption, elution, blocking, and counterblocking uniquely determine antigens and antibodies. There is no restriction on cross-reactivity. The protocol for counterblocking was given by Denniston and has not been developed by serologists. Denniston has shown that counterblocking can be replaced by combinations ofthe other operations in a system where there can be no cross-reactivity. This paper indicates the potential usefulness of such a technique.

In a first order abstract immunogenetic system solutions to the problem of finding basic recognition factors such as antibodies or cytotoxic T-lymphocytes and basic recognized factors such as genes or gene products is given by a factorization M = ϕ 1 × G × ϕ 2 , where M is a reaction relation (matrix) and ϕ 1 labels individuals with genes, G relates genes to antibodies, and ϕ 2 labels reagents with antibodies. For a given M the problem of determining in general whether for a given n such a factorization exists with n antibodies or genes in G is NP-complete if no information other than M is available. In this paper we consider the problem of obtaining the factorization of M into ϕ 1 × G by ϕ 2 when information on effector cell combinations or reagents is given. When enough information is given it is shown that ϕ 1 × G and ϕ 2 are essentially uniquely determined, and an algorithm to obtain them in polynomial time is given. We also relate the computations necessary to uncover an antibody to its behavior in reaction tests. Based on this theory, a best possible solution is also given in cases where not enough information is available to obtain the unique solution.

In two recent papers the authors introduced some new approaches to the problem of modeling the phenomena underlying immunological reaction tests. These approaches allow one to easily construct the best possible models for a given amount of immunological test data. In the first paper the authors used a purely Boolean approach, i.e., it was assumed that the experimenter signified whether or not a reaction occurred in a given test. In the second paper the authors assumed that the relative strengths of the reactions were available as data for the modeling process. They showed that in this case strictly better models could be constructed. This paper generalizes the approaches taken in the first two papers and provides a unified approach to this whole subject. Many of the results, e.g., the ability to construct the best model, of the first two papers hold in this more general setting. Moreover, this generalization allows one to assess the tradeoffs involved in using data on the relative strengths of reactions. In particular, we see that using relative strengths is equivalent to using an additional intersection factor in a strictly Boolean approach. This intersection factor it turns out, can be obtained experimentally by using elution in addition to the absorption involved in the first two papers. Finally, the duality between fragments and cofragments becomes apparent using this approach.

This paper summarizes approaches to developing mathematics that can act as a language for immunogenetics. The need for this has been documented by showing inadequacies of the standard symbolism. Apparent distinctions in symbolizing and conceptualizing factors involved in immunogenetics are seen to disappear in the mathematical models presented here. One model, a three-fold Boolean matrix factorization, subsumes all approaches to the idea of specificity and yet is general enough to incorporate data beyond that found only in a reaction matrix.

We show that the usual construction of the free distributive lattice on n generators generalizes to an arbitrary quantity of generators and actually yields a free completely distributive lattice. Furthermore, for an infinite number of generators the cardinality of the corresponding free completely distributive lattice is exactly that of the power set of the power set of the set of generators.