2008年2月
Inferring pedigree graphs from genetic distances
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- ,
- 巻
- E91D
- 号
- 2
- 開始ページ
- 162
- 終了ページ
- 169
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietisy/e91-d.2.162
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
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.
- リンク情報
-
- DOI
- https://doi.org/10.1093/ietisy/e91-d.2.162
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902205044112070
- CiNii Articles
- http://ci.nii.ac.jp/naid/10026800855
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000253655800002&DestApp=WOS_CPL
- ID情報
-
- DOI : 10.1093/ietisy/e91-d.2.162
- ISSN : 0916-8532
- J-Global ID : 200902205044112070
- CiNii Articles ID : 10026800855
- Web of Science ID : WOS:000253655800002