A Hopfield-Type Neural Network for Haplotype Assembly Problem

Haplotype reconstruction based on aligned SNP fragments is to infer a pair of haplotypes from localized polymorphism data got through short genome fragment assembly. For this problem, one of important computational models is the minimum fragment removal (MFR) model. This model constructs a pair of haplotypes by deleting minimum fragments from the data set so that left fragments can be classified into two sets in which there is no confliction. In this paper, a Hopfield-type neural network based on this model is proposed. This algorithm classifies all fragments into three sets. The fragments in set 1 and set 2 are used to construct a pair of haplotypes, and the third set contains the fragments that should be removed. In addition, in order to improve its performance, a preprocessing method is proposed, and different dynamics are used for different type neurons. The performance of this proposed algorithm is verified by experiments on real data.