Globally Optimal Classification and Pairing of Human Chromosomes

We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in polynomial time. In addition, we propose a technique of homologue pairing via maximum-weight graph matching. It obtains the globally optimal solution by forming all homologue pairs simultaneously under a maximum likelihood criterion, rather than finding one pair at a time as in existing heuristic algorithms. After the optimal homologue pairing, chromosome classification can also be done by maximum-weight graph matching. This new graph theoretical approach to chromosome pairing and classification is more robust than the transportation algorithm, because many attributes of a chromosome have less variations within a cell than between different cells.