Cargando…

Efficient path-based computations on pedigree graphs with compact encodings

A pedigree is a diagram of family relationships, and it is often used to determine the mode of inheritance (dominant, recessive, etc.) of genetic diseases. Along with rapidly growing knowledge of genetics and accumulation of genealogy information, pedigree data is becoming increasingly important. In...

Descripción completa

Detalles Bibliográficos
Autores principales: Yang, Lei, Cheng, En, Özsoyoğlu, Z Meral
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2012
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3311099/
https://www.ncbi.nlm.nih.gov/pubmed/22536898
http://dx.doi.org/10.1186/1471-2105-13-S3-S14
_version_ 1782227746430124032
author Yang, Lei
Cheng, En
Özsoyoğlu, Z Meral
author_facet Yang, Lei
Cheng, En
Özsoyoğlu, Z Meral
author_sort Yang, Lei
collection PubMed
description A pedigree is a diagram of family relationships, and it is often used to determine the mode of inheritance (dominant, recessive, etc.) of genetic diseases. Along with rapidly growing knowledge of genetics and accumulation of genealogy information, pedigree data is becoming increasingly important. In large pedigree graphs, path-based methods for efficiently computing genealogical measurements, such as inbreeding and kinship coefficients of individuals, depend on efficient identification and processing of paths. In this paper, we propose a new compact path encoding scheme on large pedigrees, accompanied by an efficient algorithm for identifying paths. We demonstrate the utilization of our proposed method by applying it to the inbreeding coefficient computation. We present time and space complexity analysis, and also manifest the efficiency of our method for evaluating inbreeding coefficients as compared to previous methods by experimental results using pedigree graphs with real and synthetic data. Both theoretical and experimental results demonstrate that our method is more scalable and efficient than previous methods in terms of time and space requirements.
format Online
Article
Text
id pubmed-3311099
institution National Center for Biotechnology Information
language English
publishDate 2012
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-33110992012-04-02 Efficient path-based computations on pedigree graphs with compact encodings Yang, Lei Cheng, En Özsoyoğlu, Z Meral BMC Bioinformatics Proceedings A pedigree is a diagram of family relationships, and it is often used to determine the mode of inheritance (dominant, recessive, etc.) of genetic diseases. Along with rapidly growing knowledge of genetics and accumulation of genealogy information, pedigree data is becoming increasingly important. In large pedigree graphs, path-based methods for efficiently computing genealogical measurements, such as inbreeding and kinship coefficients of individuals, depend on efficient identification and processing of paths. In this paper, we propose a new compact path encoding scheme on large pedigrees, accompanied by an efficient algorithm for identifying paths. We demonstrate the utilization of our proposed method by applying it to the inbreeding coefficient computation. We present time and space complexity analysis, and also manifest the efficiency of our method for evaluating inbreeding coefficients as compared to previous methods by experimental results using pedigree graphs with real and synthetic data. Both theoretical and experimental results demonstrate that our method is more scalable and efficient than previous methods in terms of time and space requirements. BioMed Central 2012-03-21 /pmc/articles/PMC3311099/ /pubmed/22536898 http://dx.doi.org/10.1186/1471-2105-13-S3-S14 Text en Copyright ©2012 Yang et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Proceedings
Yang, Lei
Cheng, En
Özsoyoğlu, Z Meral
Efficient path-based computations on pedigree graphs with compact encodings
title Efficient path-based computations on pedigree graphs with compact encodings
title_full Efficient path-based computations on pedigree graphs with compact encodings
title_fullStr Efficient path-based computations on pedigree graphs with compact encodings
title_full_unstemmed Efficient path-based computations on pedigree graphs with compact encodings
title_short Efficient path-based computations on pedigree graphs with compact encodings
title_sort efficient path-based computations on pedigree graphs with compact encodings
topic Proceedings
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3311099/
https://www.ncbi.nlm.nih.gov/pubmed/22536898
http://dx.doi.org/10.1186/1471-2105-13-S3-S14
work_keys_str_mv AT yanglei efficientpathbasedcomputationsonpedigreegraphswithcompactencodings
AT chengen efficientpathbasedcomputationsonpedigreegraphswithcompactencodings
AT ozsoyogluzmeral efficientpathbasedcomputationsonpedigreegraphswithcompactencodings