Genetic algorithm for haplotyping and block partitioning

A new algorithm for performing simultaneous haplotype resolution and block partitioning is proposed. The algorithm is based on genetic algorithm approach and the parsimonious principle. The multiloculs LD measure (Normalized Entropy Difference) is used as a block identification criterion. The proposed algorithm incorporates missing data is a part of the model and allows blocks of arbitrary length. In addition, the algorithm provides scores for the block boundaries which represent measures of strength of the boundaries at specific positions. The results show that the proposed genetic algorithm provides the accuracy of haplotype decomposition within the range of the same indicators shown by the other algorithms. The proposed algorithm is also used in a new population clustering algorithm, which extracts from the given genotype sample two clusters with substantially different block structures and finds haplotype resolution and block partitioning for each cluster.

Autorentext

Nadezhda Sazonova received her Masters degrees in Mathematics, Statistics and Economics from West Virginia University in 2002, received her PhD degree in Computer Science from the same university in 2007. Her main research intersts include statistical pattern recognition with applications in bioinformatics, biomedicine and biometrics.