Haplotype Block Partitioning using a Normalized Maximum Likelihood Model

This paper proposes a new method for finding block structure in haplotypes. The new method belongs to the family of minimum description length (MDL) methods, which were intensively investigated in connection with this problem also in the past. Within MDL paradigm we evaluate the code length by using the normalized maximum likelihood (NML) model, as opposed to two part codes used in the past, resulting in a more compact conditional description. Also we propose a new joint clustering and encoding algorithm which selects the cluster centers by minimizing the overall code length when encoding the cluster centers (block prototypes) and the blocks conditional on the block prototypes. The minimized description length provided by the new algorithm is shown to be smaller than that obtained by previous methods when applied to real haplo-type data. The inference of the block boundaries using this better code length measure produces different results than the previous methods, reducing significantly the description length of the overall haplotype partition.