title: Comparing Unlabeled Pedigree Graphs via Covering with Bipartite and Path.
abstract: Family trees, also called pedigrees, have important information about an individual's past and future life. It can be used as a diagnostic tool and help guide decisions about genetic testing for the patient and at-risk family members. There are 2% to 10% of parent-child relationships missing, and this can cause large differences in the pedigree graphs created. Hence, the evaluation of pedigrees is an essential task. In this article, we focus on the problem of isomorphism of unlabeled subpedigrees with a large number of individuals and hundreds of families, given that the two pedigrees being evaluated are generational and mating is between external parents. We address two restricted versions of the unlabeled subpedigree graph problem, Cover Unlabeled subPedigree with a Bipartite graph (CUPB), and Cover Unlabeled subPedigree with a Path (CUPP) problems. Fixed parameter algorithms are presented to solve the two problems, CUPB and CUPP.
authors.affiliation: 1 Informatic Research Institute , City SRTA, Alexandria, Egypt .|2 Department of Mathematics and Computer Science, Faculty of Science, Alexandria University , Alexandria, Egypt .
authors.forename: Lamiaa A
authors.initials: LA
authors.lastname: Amar
authors.affiliation: 3 Department of Computer Science, College of Computing and Information Technology , Arab Academy for Science, Technology, and Maritime Transport, Alexandria, Egypt .
authors.forename: Nahla A
authors.initials: NA
authors.lastname: Belal
authors.affiliation: 4 Informatic Research Institute , City of SRTA, Alexandria, Egypt .
authors.forename: Shaheera
authors.initials: S
authors.lastname: Rashwan
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D005260:Female; D005820:Genetic Testing; D006801:Humans; D008297:Male; D010375:Pedigree
keywords: bipartite graph; isomorphism; unlabeled pedigree