Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Foundations of Computer Science -- Papers -- Graph Algorithms |
Inferring Pedigree Graphs from Genetic Distances
1 The author is with Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji-shi, 611–0011 Japan. E-mail: tamura{at}kuicr.kyoto-u.ac.jp, 2 The author is with the Graduate School of Informatics, Kyoto University, Kyoto-shi, 606–8501 Japan.
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.
Key Words: algorithm, directed acyclic graph, distance matrix, pedigree, genetic distance
Manuscript received March 30, 2007. Manuscript revised June 22, 2007.
Reference
[1] L. Aceto, J.A. Hansen, A. Ingolfsdottir, J. Johnsen, and J. Knudsen, "The complexity of checking consistency of pedigree information and related problems," J. Comput. Sci. Technol., vol.19, no.1, pp.42–59, 2004. [2] A.V. Aho, Y. Sagiv, T.G. Szymanski, and J.D. Ullman, "Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions," SIAM J. Comput., vol.10, no.3, pp.405–421, 1981. [3] I. Althofer, "On optimal realizations of finite metric spaces by graphs," Discrete Comput. Geom., vol.3, pp.103–122, 1988. [4] V. Berry and O. Gascuel, "Inferring evolutionary trees with strong combinatorial evidence," Theor. Comput. Sci., vol.240, no.2, pp.271–298, 2000. [5] D. Bryant and J. Lagergren, "Compatibility of unrooted phylogenetic trees is FPT," Theor. Comput. Sci., vol.351, no.3, pp.296–302, 2006. [6] C. Choy, J. Jansson, K. Sadakane, and W.K. Sung, "Computing the maximum agreement of phylogenetic networks," Electr. Notes Theor. Comput. Sci, vol.91, pp.134–147, 2004. [7] J. Felsenstein, "Numerical methods for inferring evolutionary trees," Quarterly Review on Biology, vol.57, no.4, pp.379–404, 1982. [8] J. Felsenstein, "PHYLIP: Phylogeny inference package (version 3.2)," Cladistics, vol.5, pp.164–166, 1989. [9] D.F. Feng and R.F. Doolittle, "Progressive alignment of amino acid sequences and construction of phylogenetic trees from them," Methods Enzymol, vol.266, pp.368–382, 1996. [10] W.M. Fitch, "Toward defining the course of evolution: Minimal change for a specific tree topology," Systematic Zoology, vol.20, pp.406–441, 1971. [11] W.M. Fitch and E. Margoliash, "Construction of phylogenetic trees," Science, vol.155, pp.279–284, 1987. [12] D. Gusfield, "Efficient algorithms for inferring evolutionary trees," Networks, vol.21, pp.19–28, 1991. [13] D. Gusfield, S. Eddhu, and C. Langley, "Efficient reconstruction of phylogenetic networks with constrained recombination," Proc. LSS/IEEE Computer Society Bioinformatics Conference, pp.363–374, 2003. [14] D. Gusfield, D. Hickerson, and S. Eddhu, "An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study," Discrete Appl. Math., vol.155, no.6–7, pp.806–830, 2007. [15] S.L. Hakimi and S.S. Yau, "Distance matrix of a graph and its realizability," Quart. Appl. Math., vol.22, pp.305–317, 1965. [16] Y.J. He, T.N.D. Huynh, J. Jansson, and W.K. Sung, "Inferring phylogenetic relationships avoiding forbidden rooted triplets," J. Bioinformatics and Computational Biology, vol.4, no.1, pp.59–74, 2006. [17] D.H. Huson, T. Dezulian, T. Klopper, and M.A. Steel, "Phylogenetic super-networks from partial trees," IEEE/ACM Trans. Comput. Biology Bioinform, vol.1, no.4, pp.151–158, 2004. [18] J. Jansson and W.K. Sung, "Inferring a level-1 phylogenetic network from a dense set of rooted triplets," Theor. Comput. Sci., vol.363, no.1, pp.60–68, 2006. [19] J. Jansson and W.K. Sung, "The maximum agreement of two nested phylogenetic networks," Proc. International Symposium on Algorithms and Computation, pp.581–593, 2004. [20] J. Li and T. Jiang, "Computing the minimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer linear programming," Journal of Computational Biology, vol.12, no.6, pp.719–739, 2005. [21] V. Makarenkov and P. Legendre, "From a phylogenetic tree to a reticulated network," Journal of Computational Biology, vol.11, no.1, pp.195–212, 2004. [22] E. Masood, "Gene warrior," New Scientist, Magazine issue 2247, July 2000. [23] A. Piccolboni and D. Gusfield, "On the complexity of fundamental computational problems in pedigree analysis," Journal of Computational Biology, vol.10, no.5, pp.763–773, 2003. [24] C. Semple and M. Steel, Phylogenetics, Oxford University Press, 2003. [25] S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, pp.175, Addison-Wesley, Reading, MA, 1990. [26] L. Wang, K. Zhang, and L. Zhang, "Perfect phylogenetic networks with recombination," Journal of Computational Biology, vol.8, no.1, pp.69–78, 2001.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by TAMURA, T.
Articles by ITO, H.
Search for Related Content
Social Bookmarking
What's this?