Publication Details
Title: Pedigree Reconstruction Using Identity by Descent
Author: B. Kirkpatrick, S. C. Li, R. M. Karp, and E. Halperin
Group: Algorithms
Date: March 2011
PDF: http://www.icsi.berkeley.edu/pubs/algorithms/ICSI_pedigreereconstruction12.pdf
Overview:
Can we find the family trees, or pedigrees, that relate the haplotypes of a group of individu- als? Collecting the genealogical information for how individuals are related is a very time-consuming and expensive process. Methods for automating the construction of pedigrees could stream-line this process. While constructing single-generation families is relatively easy given whole genome data, reconstructing multi-generational, possibly inbred, pedigrees is much more challenging. This paper addresses the important question of reconstructing monogamous, regular pedigrees, where pedigrees are regular when individuals mate only with other individuals at the same generation. This pa- per introduces two multi-generational pedigree reconstruction methods: one for inbreeding relationships and one for outbreeding relationships. In contrast to previous methods that focused on the independent estimation of relationship distances between every pair of typed individuals, here we present methods that aim at the reconstruction of the entire pedigree. We show that both our methods out-perform the state-of-the-art and that the outbreeding method is capable of reconstructing pedigrees at least six generations back in time with high accuracy. The two programs are available at http://cop.icsi.berkeley.edu/cop/.
Acknowledgements:
This work was partially supported by funding provided through a National Science Foundation Graduate Research Grant and through National Science Foundation grant CCF : 1052553 (“Systematic Construction of Heuristic Algorithms for Combinatiorial Optimization Problems in Biology"). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation.
Bibliographic Information:
Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011),Vancouver, British Columbia, Canada, pp. 136-152. Also appeared in Journal of Computational Biology, Vol. 18, No. 11, pp. 1481-1493, November 2011.
Bibliographic Reference:
B. Kirkpatrick, S. C. Li, R. M. Karp, and E. Halperin. Pedigree Reconstruction Using Identity by Descent. Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011),Vancouver, British Columbia, Canada, pp. 136-152. Also appeared in Journal of Computational Biology, Vol. 18, No. 11, pp. 1481-1493, November 2011., March 2011
Author: B. Kirkpatrick, S. C. Li, R. M. Karp, and E. Halperin
Group: Algorithms
Date: March 2011
PDF: http://www.icsi.berkeley.edu/pubs/algorithms/ICSI_pedigreereconstruction12.pdf
Overview:
Can we find the family trees, or pedigrees, that relate the haplotypes of a group of individu- als? Collecting the genealogical information for how individuals are related is a very time-consuming and expensive process. Methods for automating the construction of pedigrees could stream-line this process. While constructing single-generation families is relatively easy given whole genome data, reconstructing multi-generational, possibly inbred, pedigrees is much more challenging. This paper addresses the important question of reconstructing monogamous, regular pedigrees, where pedigrees are regular when individuals mate only with other individuals at the same generation. This pa- per introduces two multi-generational pedigree reconstruction methods: one for inbreeding relationships and one for outbreeding relationships. In contrast to previous methods that focused on the independent estimation of relationship distances between every pair of typed individuals, here we present methods that aim at the reconstruction of the entire pedigree. We show that both our methods out-perform the state-of-the-art and that the outbreeding method is capable of reconstructing pedigrees at least six generations back in time with high accuracy. The two programs are available at http://cop.icsi.berkeley.edu/cop/.
Acknowledgements:
This work was partially supported by funding provided through a National Science Foundation Graduate Research Grant and through National Science Foundation grant CCF : 1052553 (“Systematic Construction of Heuristic Algorithms for Combinatiorial Optimization Problems in Biology"). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation.
Bibliographic Information:
Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011),Vancouver, British Columbia, Canada, pp. 136-152. Also appeared in Journal of Computational Biology, Vol. 18, No. 11, pp. 1481-1493, November 2011.
Bibliographic Reference:
B. Kirkpatrick, S. C. Li, R. M. Karp, and E. Halperin. Pedigree Reconstruction Using Identity by Descent. Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011),Vancouver, British Columbia, Canada, pp. 136-152. Also appeared in Journal of Computational Biology, Vol. 18, No. 11, pp. 1481-1493, November 2011., March 2011