IEICE TRANSACTIONS on Information
Inferring Pedigree Graphs from Genetic Distances
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.2 pp.162-169
- Publication Date
- 2008/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e91-d.2.162
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeyuki TAMURA, Hiro ITO, "Inferring Pedigree Graphs from Genetic Distances" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 2, pp. 162-169, February 2008, doi: 10.1093/ietisy/e91-d.2.162.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.2.162/_p
Copy
@ARTICLE{e91-d_2_162,
author={Takeyuki TAMURA, Hiro ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Inferring Pedigree Graphs from Genetic Distances},
year={2008},
volume={E91-D},
number={2},
pages={162-169},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e91-d.2.162},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Inferring Pedigree Graphs from Genetic Distances
T2 - IEICE TRANSACTIONS on Information
SP - 162
EP - 169
AU - Takeyuki TAMURA
AU - Hiro ITO
PY - 2008
DO - 10.1093/ietisy/e91-d.2.162
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2008
AB - 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.
ER -
English
