Inferring Pedigree Graphs from Genetic Distances

Takeyuki TAMURA  Hiro ITO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.2   pp.162-169
Publication Date: 2008/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.2.162
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
algorithm,  directed acyclic graph,  distance matrix,  pedigree,  genetic distance,  

Full Text: PDF(258.3KB)>>
Buy this Article



Summary: 
In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.