IPED2: Inheritance Path based Pedigree Reconstruction Algorithm for Complicated Pedigrees

IPED2: Inheritance Path based Pedigree Reconstruction Algorithm for Complicated Pedigrees

Dan He, Zhanyong Wang, Laxmi Parida, Eleazar Eskin
(Submitted on 23 Aug 2014)

Reconstruction of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. The problem is known to be NP-hard even for datasets known to only contain siblings. Some recent methods have been developed to accurately and efficiently reconstruct pedigrees. These methods, however, still consider relatively simple pedigrees, for example, they are not able to handle half-sibling situations where a pair of individuals only share one parent. In this work, we propose an efficient method, IPED2, based on our previous work, which specifically targets reconstruction of complicated pedigrees that include half-siblings. We note that the presence of half-siblings makes the reconstruction problem significantly more challenging which is why previous methods exclude the possibility of half-siblings. We proposed a novel model as well as an efficient graph algorithm and experiments show that our algorithm achieves relatively accurate reconstruction. To our knowledge, this is the first method that is able to handle pedigree reconstruction based on genotype data only when half-sibling exists in any generation of the pedigree.

1 thought on “IPED2: Inheritance Path based Pedigree Reconstruction Algorithm for Complicated Pedigrees

  1. This is an absolutely necessary step forward in order to have a useful program for pedigree reconstruction from genetic data. However, IPED2 and PREPARE (another program very similar to IPED2) can only reconstruct pedigrees if all the genotyped samples are in the same and last generation. In other words, if you have a trio (two parents and a child), then they will not be able to reconstruct that very basic, fundamental pedigree.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s