Uncovering Antibody Incidence Structures

<p> 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 <i> M </i> =&varphi; ₁ x G x &varphi; ₂ , where <i> M </i> is a reaction relation (matrix) and &varphi; ₁ labels individuals with genes, G relates genes to antibodies, and &varphi; ₂ labels reagents with antibodies. For a given <i> M </i> the problem of determining in general whether for a given <i> n </i> such a factorization exists with <i> n </i> antibodies or genes in G is NP-complete if no information other than <i> M </i> is available. In this paper we consider the problem of obtaining the factorization of <i> M </i> into &varphi; ₁ x G by &varphi; ₂ when information on effector cell combinations or reagents is given. When enough information is given it is shown that &varphi; ₁ x G and &varphi; ₂ 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.</p>