Uncovering Antibody Incidence Structures

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 x G x ϕ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 x G by ϕ2 when information on effector cell combinations or reagents is given. When enough information is given it is shown that ϕ1 x 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