Title: Fast chromosome karyotyping by auction algorithm

Authors: Xiaolin Wu, Sorina Dumitrescu, Pravesh Biyani, Qiang Wu

Addresses: Department of Electrical and Computer Engineering, McMaster University, Hamilton, ON L8S 4K1, Canada. ' Department of Electrical and Computer Engineering, McMaster University, Hamilton, ON L8S 4K1, Canada. ' PLOT 5, 66/1, Motorola India Electronics Ltd., Bagmane Tech Park, C.V Raman Nagar, Bangalore 560093, India. ' Advanced Digital Imaging Research, LLC 2450 South Shore Boulevard, Suite 305, League City TX 77573, USA

Abstract: 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.

Keywords: chromosome karyotyping; maximum likelihood classification; auction algorithm; optimisation; bioinformatics; human chromosomes.

DOI: 10.1504/IJBRA.2005.007911

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.3, pp.351 - 362

Published online: 30 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article