A note on algorithms for genotype and allele elimination in complex pedigrees with incomplete genotype data

Elimination of genotypes or alleles for each individual or meiosis, which are inconsistent with observed genotypes, is a component of various genetic analyses of complex pedigrees. Computational efficiency of the elimination algorithm is critical in some applications such as genotype sampling via descent graph Markov chains. We present an allele elimination algorithm and two genotype elimination algorithms for complex pedigrees with incomplete genotype data. We modify all three algorithms to incorporate inheritance restrictions imposed by a complete or incomplete descent graph such that every inconsistent complete descent graph is detected in any pedigree, and every inconsistent incomplete descent graph is detected in any pedigree without loops with the genotype elimination algorithms. Allele elimination requires less CPU time and memory, but does not always eliminate all inconsistent alleles, even in pedigrees without loops. The first genotype algorithm produces genotype lists for each individual, which are identical to those obtained from the Lange-Goradia algorithm, but exploits the half-sib structure of some populations and reduces CPU time. The second genotype elimination algorithm deletes more inconsistent genotypes in pedigrees with loops and detects more illegal, incomplete descent graphs in such pedigrees.     

An algorithm for automatic genotype elimination.

Automatic genotype elimination algorithms for a single locus play a central role in making likelihood computations on human pedigree data feasible. We present a simple algorithm that is fully efficient in pedigrees without loops. This algorithm can be easily coded and has been instrumental in greatly reducing computing times for pedigree analysis. A contrived counter-example demonstrates that some superfluous genotypes cannot be excluded for inbred pedigrees.     

An algorithm to approximate the likelihood for pedigree data with loops by cutting

This paper presents a recursive algorithm to approximate the likelihood in arbitrary pedigrees with loops. The algorithm handles any number and nesting levels of loops in pedigrees. The loops are cut as described in a previous publication and the approximate likelihood is simultaneously computed using the cut pedigree. No identification of a loop in the pedigree is necessary before the algorithm is applied.     

Breaking loops in large complex pedigrees

For pedigrees with multiple loops, exact likelihoods could not be computed in an acceptable time frame and thus, approximate methods are used. Some of these methods are based on breaking loops and approximations of complex pedigree likelihoods using the exact likelihood of the corresponding zero-loop pedigree. Due to ignoring loops, this method results in a loss of genetic information and a decrease in the power to detect linkage. To minimize this loss, an optimal set of loop breakers has to be selected. In this paper, we present a graph theory based algorithm for automatic selection of an optimal set of loop breakers. We propose using a total relationship between measured pedigree members as a proxy to power. To minimize the loss of genetic information, we suggest selection of such breakers whose duplication in a pedigree would be accompanied by a minimal loss of total relationship between measured pedigree members. We show that our algorithm compares favorably with other existing loop-breaker selection algorithms in terms of conservation of genetic information, statistical power and CPU time of subsequent linkage analysis. We implemented our method in a software package LOOP_EDGE, which is available at http://mga.bionet.nsc.ru/nlru/.     

Efficient genotype elimination via adaptive allele consolidation

We propose the technique of Adaptive Allele Consolidation, that greatly improves the performance of the Lange-Goradia algorithm for genotype elimination in pedigrees, while still producing equivalent output. Genotype elimination consists in removing from a pedigree those genotypes that are impossible according to the Mendelian law of inheritance. This is used to find errors in genetic data and is useful as a preprocessing step in other analyses (such as linkage analysis or haplotype imputation). The problem of genotype elimination is intrinsically combinatorial, and Allele Consolidation is an existing technique where several alleles are replaced by a single “lumped” allele in order to reduce the number of combinations of genotypes that have to be considered, possibly at the expense of precision. In existing Allele Consolidation techniques, alleles are lumped once and for all before performing genotype elimination. The idea of Adaptive Allele Consolidation is to dynamically change the set of alleles that are lumped together during the execution of the Lange-Goradia algorithm, so that both high performance and precision are achieved. We have implemented the technique in a tool called Celer and evaluated it on a large set of scenarios, with good results.     

Selecting loop breakers in general pedigrees

The presence of loops in pedigrees poses severe computational problems in likelihood calculation that can be solved by creating an equivalent unlooped pedigree. We introduce a heuristic polynomial-time dynamic-programming algorithm, called SFH, that addresses the problem of selecting a minimal-cost set of loop breakers. We report computational experiments on simulated pedigrees with up to 1000 individuals and 361 loops, and multiple marriages. We compare the loop-breaker set selected by our method with that obtained using the software package FASTLINK 4.1P. Our approach outperforms FASTLINK 4.1P on the computational-time point of view, on the point of view of quality of the loop-breaker set obtained, and on the point of view of the size of the problem that can be addressed.     

Conditional probability methods for haplotyping in pedigrees

Efficient haplotyping in pedigrees is important for the fine mapping of quantitative trait locus (QTL) or complex disease genes. To reconstruct haplotypes efficiently for a large pedigree with a large number of linked loci, two algorithms based on conditional probabilities and likelihood computations are presented. The first algorithm (the conditional probability method) produces a single, approximately optimal haplotype configuration, with computing time increasing linearly in the number of linked loci and the pedigree size. The other algorithm (the conditional enumeration method) identifies a set of haplotype configurations with high probabilities conditional on the observed genotype data for a pedigree. Its computing time increases less than exponentially with the size of a subset of the set of person-loci with unordered genotypes and linearly with its complement. The size of the subset is controlled by a threshold parameter. The set of identified haplotype configurations can be used to estimate the identity-by-descent (IBD) matrix at a map position for a pedigree. The algorithms have been tested on published and simulated data sets. The new haplotyping methods are much faster and provide more information than several existing stochastic and rule-based methods. The accuracies of the new methods are equivalent to or better than those of these existing methods.     

An approximation to the likelihood for a pedigree with loops

This paper presents a new approximation to the likelihood for a pedigree with loops, based on cutting all loops and extending the pedigree at the cuts. An opimum loop-cutting strategy and an iterative extension technique are presented. The likelihood for a pedigree with loops is then approximated by the conditional likelihood for the entire cut-extended pedigree given the extended part. The approximate likelihoods are compared with the exact likelihoods obtained using the program MENDEL for several small pedigrees with loops. The approximation is efficient for large pedigrees with complex loops in terms of computing speed and memory requirements.     

An efficient algorithm for estimation of functions of a pedigree with short inbred loops

The study is a further development of the methods for genetic analysis using pedigree data. Methods for approximation of the likelihood based on cutting of all loops are often used in analysis of large pedigrees with multiple loops. In this study, a fast efficient algorithm for calculating likelihood is proposed. This algorithm allows short inbred loops to be processed without cutting them and, hence, prevents the loss of genetic information. The approach proposed may be important for analysis of the pedigrees of farm and laboratory animals, where inbred crosses resulting in short inbred loops are common. The results of a stochastic genetic experiment agree with this suggestion: the use of the algorithm proposed considerably increases the accuracy of estimation of model parameters and testing of genetic hypotheses.     

FamSeq: A Variant Calling Program for Family-Based Sequencing Data Using Graphics Processing Units

Various algorithms have been developed for variant calling using next-generation sequencing data, and various methods have been applied to reduce the associated false positive and false negative rates. Few variant calling programs, however, utilize the pedigree information when the family-based sequencing data are available. Here, we present a program, FamSeq, which reduces both false positive and false negative rates by incorporating the pedigree information from the Mendelian genetic model into variant calling. To accommodate variations in data complexity, FamSeq consists of four distinct implementations of the Mendelian genetic model: the Bayesian network algorithm, a graphics processing unit version of the Bayesian network algorithm, the Elston-Stewart algorithm and the Markov chain Monte Carlo algorithm. To make the software efficient and applicable to large families, we parallelized the Bayesian network algorithm that copes with pedigrees with inbreeding loops without losing calculation precision on an NVIDIA graphics processing unit. In order to compare the difference in the four methods, we applied FamSeq to pedigree sequencing data with family sizes that varied from 7 to 12. When there is no inbreeding loop in the pedigree, the Elston-Stewart algorithm gives analytical results in a short time. If there are inbreeding loops in the pedigree, we recommend the Bayesian network method, which provides exact answers. To improve the computing speed of the Bayesian network method, we parallelized the computation on a graphics processing unit. This allowed the Bayesian network method to process the whole genome sequencing data of a family of 12 individuals within two days, which was a 10-fold time reduction compared to the time required for this computation on a central processing unit.

This is a PLOS Computational Biology Software Article

     

An algorithm for sampling descent graphs in large complex pedigrees efficiently

No exact method for determining genotypic and identity-by-descent probabilities is available for large complex pedigrees. Approximate methods for such pedigrees cannot be guaranteed to be unbiased. A new method is proposed that uses the Metropolis-Hastings algorithm to sample a Markov chain of descent graphs which fit the pedigree and known genotypes. Unknown genotypes are determined from each descent graph. Genotypic probabilities are estimated as their means. The algorithm is shown to be unbiased for small complex pedigrees and feasible and consistent for moderately large complex pedigrees.     

The art of pedigree drawing: algorithmic aspects

MOTIVATION: Giving a meaningful representation of a pedigree is not obvious when it includes consanguinity loops, individuals with multiple mates or several related families. RESULTS: We show that finding a perfectly meaningful representation of a pedigree is equivalent to the interval graph sandwich problem and we propose an algorithm for drawing pedigrees.     

An efficient algorithm to compute the posterior genotypic distribution for every member of a pedigree without loops

This paper describes a non-iterative, recursive method to compute the likelihood for a pedigree without loops, and hence an efficient way to compute genotype probabilities for every member of the pedigree. The method can be used with multiple mates and large sibships. Scaling is used in calculations to avoid numerical problems in working with large pedigrees.     

Madeline 2.0 PDE: a new program for local and web-based pedigree drawing

The Madeline 2.0 Pedigree Drawing Engine (PDE) is a pedigree drawing program for use in linkage and family-based association studies. The program is designed to handle large and complex pedigrees with an emphasis on readability and aesthetics. For complex pedigrees, we use a hybrid algorithm in which consanguinous loops are drawn as cyclic graphs whenever possible, but we resort to acyclic graphs when matings can no longer be connected without line crossings. A similar hybrid approach is used to avoid line crossings for matings between distant descendants of different founding groups. Written in object-oriented C++ and released under the GNU General Public License (GPL), Madeline 2.0 PDE reads input files specified on the command line and generates pedigree drawings without user interaction. Pedigree output in scalable vector graphics (SVG) format can be viewed in browsers with native SVG rendering support or in vector graphics editors. We provide an easy-to-use public web service, which is experimental and still under development. Availability: http://kellogg.umich.edu/madeline.     

An algorithm of step-by-step pedigree drawing

An algorithm for drawing large, complex pedigrees containing inbred loops and multiple-mate families is presented. The algorithm is based on a step-by-step approach to imaging, when the researcher determines the direction of further extension of the scheme. The algorithm is implemented as the PedigreeQuery software package written in Java. The software has a convenient graphical interface. The software package permits constructing not only whole pedigrees, but also their fragments that are particularly interesting for research. It also allows for adding new information on the phenotypes and genotypes of pedigree members. PedigreeQuery is distributed free of charge; it is available at http://mga.bionet.msc.ru/PedigreeQuery/PedigreeQuery.html and ftp://mga.bionet.msc.ru/PedigreeQuery/.     

An Algorithm of Step-by-step Pedigree Drawing

An algorithm for drawing large, complex pedigrees containing inbred loops and multiple-mate families is presented. The algorithm is based on a step-by-step approach to imaging, when the researcher determines the direction of further extension of the scheme. The algorithm is implemented as the PedigreeQuery software package written in Java. The software has a convenient graphical interface. The software package permits constructing not only whole pedigrees, but also their fragments that are particularly interesting for research. It also allows for adding new information on the phenotypes and genotypes of pedigree members. PedigreeQuery is distributed free of charge; it is available at http://mga.bionet.msc.ru/PedigreeQuery/PedigreeQuery.html and ftp://mga.bionet.nsc.ru/PedigreeQuery/.     

Computing the minimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer linear programming.

We study the problem of reconstructing haplotype configurations from genotypes on pedigree data with missing alleles under the Mendelian law of inheritance and the minimum-recombination principle, which is important for the construction of haplotype maps and genetic linkage/association analyses. Our previous results show that the problem of finding a minimum-recombinant haplotype configuration (MRHC) is in general NP-hard. This paper presents an effective integer linear programming (ILP) formulation of the MRHC problem with missing data and a branch-and-bound strategy that utilizes a partial order relationship and some other special relationships among variables to decide the branching order. Nontrivial lower and upper bounds on the optimal number of recombinants are introduced at each branching node to effectively prune the search tree. When multiple solutions exist, a best haplotype configuration is selected based on a maximum likelihood approach. The paper also shows for the first time how to incorporate marker interval distance into a rule-based haplotyping algorithm. Our results on simulated data show that the algorithm could recover haplotypes with 50 loci from a pedigree of size 29 in seconds on a Pentium IV computer. Its accuracy is more than 99.8% for data with no missing alleles and 98.3% for data with 20% missing alleles in terms of correctly recovered phase information at each marker locus. A comparison with a statistical approach SimWalk2 on simulated data shows that the ILP algorithm runs much faster than SimWalk2 and reports better or comparable haplotypes on average than the first and second runs of SimWalk2. As an application of the algorithm to real data, we present some test results on reconstructing haplotypes from a genome-scale SNP dataset consisting of 12 pedigrees that have 0.8% to 14.5% missing alleles.     

Simulation of pedigree genotypes by random walks.

A random walk method, based on the Metropolis algorithm, is developed for simulating the distribution of trait and linkage marker genotypes in pedigrees where trait phenotypes are already known. The method complements techniques suggested by Ploughman and Boehnke and by Ott that are based on sequential sampling of genotypes within a pedigree. These methods are useful for estimating the power of linkage analysis before complete study of a pedigree is undertaken. We apply the random walk technique to a partially penetrant disease, schizophrenia, and to a recessive disease, ataxia-telangiectasia. In the first case we show that accessory phenotypes with higher penetrance than that of schizophrenia itself may be crucial for effective linkage analysis, and in the second case we show that impressionistic selection of informative pedigrees may be misleading.     

Estimating ethnic admixture from pedigree data

This paper introduces a likelihood method of estimating ethnic admixture that uses individuals, pedigrees, or a combination of individuals and pedigrees. For each founder of a pedigree, admixture proportions are calculated by conditioning on the pedigree-wide genotypes at all ancestry-informative markers. These estimates are then propagated down the pedigree to the nonfounders by a simple averaging process. The large-sample standard errors of the founders' proportions can be similarly transformed into standard errors for the admixture proportions of the descendants. These standard errors are smaller than the corresponding standard errors when each individual is treated independently. Both hard and soft information on a founder's ancestry can be accommodated in this scheme, which has been implemented in the genetic software package Mendel. The utility of the method is demonstrated on simulated data and a real data example involving Mexican families of mixed Amerindian and Spanish ancestry.