
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Inferring Pedigree Graphs from Genetic Distances
Takeyuki TAMURA Hiro ITO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E91D
No.2
pp.162169 Publication Date: 2008/02/01 Online ISSN: 17451361
DOI: 10.1093/ietisy/e91d.2.162 Print ISSN: 09168532 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)>>
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(n^{3}) 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(n^{2}) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

