Fast chromosome karyotyping by auction algorithm

We consider the problem of automated classification of human chromosomes or karyotyping and study discrete optimisation algorithms to solve the problem as one of joint maximum likelihood classification. We demonstrate that the auction algorithm offers a simpler and more efficient solution for chromosome karyotyping than the previously known transportation algorithm, while still guaranteeing global optimality. This improvement in algorithm efficiency is made possible by first casting chromosome karyotyping into a problem of optimal assignment and then exploiting the sparsity of the assignment problem due to the inherent properties of chromosome data. Furthermore, the auction algorithm also works when the chromosome data in a cell are incomplete due to the exclusion of overlapped or severely bent chromosomes, as often encountered in routine quality data.