Efficiently calculating inbreeding on large pedigrees databases

摘要

We consider pedigree data structured in the form of a directed acyclic graph, and use an encoding scheme, called NodeCodes, for expediting the evaluation of queries on pedigree graph structures. Inbreeding is the quantitative measure of the genetic relationship between two individuals. The inbreeding coefficient is related to the probability that both copies of any given gene are received from the same ancestor. In this paper we discuss the evaluation of the inbreeding coefficient of a given individual using NodeCodes and propose a new encoding scheme, Family NodeCodes, which is further optimized for pedigree graphs. We implemented and tested these approaches on both synthetic and real pedigree data in terms of performance and scalability. Experimental results show that the use of NodeCodes provides a good alternative for queries involving the inbreeding coefficient, with significant improvements over the traditional iterative evaluation methods (up to 10.1 times faster), and Family NodeCodes further improves this to 77.1 times faster while using 91% less space than regular NodeCodes.