Joint Optimal Classification and Pairing of Human Chromosomes

Abstract

<p>In this thesis, we reexamine the problems of computer-aided classification and pairing of human chromosomes. Traditionally researchers have dealt with the problem of classification and pairing separately. In our work, we propose to jointly optimize the solutions of these two very closely related problems. The combined problem is formulated into one of optimal three-dimensional assignment with an objective function of maximum likelihood. This formulation poses two technical challenges: 1. estimation of the posterior probability that two chromosomes form a pair and the pair belongs to a class, and 2. good heuristic algorithms to solve the three-dimensional assignment problem which is NP-hard. In our work, we present various techniques to solve these problems. We also generalize our algorithms to cases where the cell data are incomplete as often encountered in practice.</p>