論文

査読有り
2008年2月

Inferring pedigree graphs from genetic distances

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
  • Takeyuki Tamura
  • ,
  • Hiro Ito

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

エクスポート
BibTeX RIS