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/.     

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.     

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.     

Extensions to pedigree analysis. V. Optimal calculation of Mendelian likelihoods

Mendelian likelihoods are computed from human pedigree data for purposes of gene mapping, risk prediction in genetic counseling, and hypothesis testing in genetic epidemiology. The Mendelian likelihood of an extended pedigree can be written as a sum of products, the sum ranging over all possible genotypic combinations for the individuals in the pedigree. Exclusion of genotypes incompatible with the phenotypic information and pedigree structure reduces the ranges of summation and simplifies the likelihood calculation. To evaluate the likelihood with the fewest possible arithmetic operations requires carrying out the summations over one individual at a time and the intervening multiplications in some appropriate order. Each such removal of an individual reduces the likelihood evaluation to another evaluation of the same numerical form. Greedy-type algorithms are suggested for determining an order in which the summations and multiplications may be carried out. The greedy methods are fast and appear to generate good removal sequences. They are shown to work well when applied to a large, complex pedigree.     

Evolutionary modelling of feed forward loops in gene regulatory networks

Feed forward loops (FFLs) are gene regulatory network motifs. They exist in different types, defined by the signs of the effects of genes in the motif on one another. We examine 36 feed forward loops in Escherichia coli, using evolutionary simulations to predict the forms of FFL expected to evolve to generate the pattern of expression of the output gene. These predictions are tested using likelihood ratios, comparing likelihoods of the observed FFL structures with their likelihoods under null models. The very high likelihood ratios generated, of over 10(11), suggest that evolutionary simulation is a valuable component in the explanation of FFL structure.     

Two new recursive likelihood calculation methods for genetic analysis

Recursive likelihood calculations for genetic analysis with ungenotyped pedigree data employ variations of the Elston-Stewart (ES) or the Lander-Green (LG) algorithms. With the ES algorithm, the number of loci may be limited but not the pedigree size. With the LG algorithm, the reverse is the case. We introduce two new algorithms for the computation of regressive likelihoods for pedigrees with multivariate traits. The first is an alternative formulation of our existing model, which leads to a simpler form in the binary trait, polygenic and mixed model cases. The second is an approximation model, which is computationally efficient. These methods apply to both continuous and binary traits, in the oligogenic and polygenic cases. Both methods coincide in the binary case. We considered these methods for cases in which all the traits are controlled by a single locus, with each trait controlled by one locus independent to the others. Simulation studies and analysis of a real data are presented for segregation analysis as illustrations. These methods can also be used in other model-based analyses. These methods are implemented in G.E.M.S., the genetic epidemiology models software.     

Flexible modeling via a hybrid estimation scheme in generalized mixed models for longitudinal data

To circumvent the computational complexity of likelihood inference in generalized mixed models that assume linear or more general additive regression models of covariate effects, Laplace's approximations to multiple integrals in the likelihood have been commonly used without addressing the issue of adequacy of the approximations for individuals with sparse observations. In this article, we propose a hybrid estimation scheme to address this issue. The likelihoods for subjects with sparse observations use Monte Carlo approximations involving importance sampling, while Laplace's approximation is used for the likelihoods of other subjects that satisfy a certain diagnostic check on the adequacy of Laplace's approximation. Because of its computational tractability, the proposed approach allows flexible modeling of covariate effects by using regression splines and model selection procedures for knot and variable selection. Its computational and statistical advantages are illustrated by simulation and by application to longitudinal data from a fecundity study of fruit flies, for which overdispersion is modeled via a double exponential family.     

Efficiency and robustness of pedigree segregation analysis.

Different pedigree structures and likelihoods are examined to determine their efficiency for parameter estimation under one-locus models. For the cases simulated, family size has little effect; estimates based on unconditional likelihoods are generally more efficient than those based on conditional likelihoods. The proposed method of pedigree analysis under a one-locus model is found to be robust in the analysis of nuclear families: skewness of the data and polygenic inheritance will not lead to the spurious detection of major loci unless they occur simultaneously, and together with a moderate amount of environmental correlation among sibs.     

A diagnostic for Cox regression with discrete failure-time models

Changes in maximum likelihood parameter estimates due to deletion of individual observations are useful statistics, both for regression diagnostics and for computing robust estimates of covariance. For many likelihoods, including those in the exponential family, these delete-one statistics can be approximated analytically from a one-step Newton-Raphson iteration on the full maximum likelihood solution. But for general conditional likelihoods and the related Cox partial likelihood, the one-step method does not reduce to an analytic solution. For these likelihoods, an alternative analytic approximation that relies on an appropriately augmented design matrix has been proposed. In this paper, we extend the augmentation approach to explicitly deal with discrete failure-time models. In these models, an individual subject may contribute information at several time points, thereby appearing in multiple risk sets before eventually experiencing a failure or being censored. Our extension also allows the covariates to be time dependent. The new augmentation requires no additional computational resources while improving results.     

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.     

An optimal algorithm for automatic genotype elimination

In an effort to accelerate likelihood computations on pedigrees, Lange and Goradia defined a genotype-elimination algorithm that aims to identify those genotypes that need not be considered during the likelihood computation. For pedigrees without loops, they showed that their algorithm was optimal, in the sense that it identified all genotypes that lead to a Mendelian inconsistency. Their algorithm, however, is not optimal for pedigrees with loops, which continue to pose daunting computational challenges. We present here a simple extension of the Lange-Goradia algorithm that we prove is optimal on pedigrees with loops, and we give examples of how our new algorithm can be used to detect genotyping errors. We also introduce a more efficient and faster algorithm for carrying out the fundamental step in the Lange-Goradia algorithm-namely, genotype elimination within a nuclear family. Finally, we improve a common algorithm for computing the likelihood of a pedigree with multiple loops. This algorithm breaks each loop by duplicating a person in that loop and then carrying out a separate likelihood calculation for each vector of possible genotypes of the loop breakers. This algorithm, however, does unnecessary computations when the loop-breaker vector is inconsistent. In this paper we present a new recursive loop breaker-elimination algorithm that solves this problem and illustrate its effectiveness on a pedigree with six loops.     

Multifactorial genetic models for quantitative traits in humans.

Quantitative traits measured in human families can be analyzed to partition the total population variance into genetic and environmental components, or to elucidate the genetic mechanism involved. We review the estimation of variance components directly from human pedigree data, or in the form of path coefficients from correlations between pairs of relatives. To elucidate genetic mechanisms, a mixed model that allows for segregation at a major locus, a polygenic effect and a sibling environmental correlation is described for nuclear families. In each case appropriate likelihoods are derived as a basis, using numerical maximum likelihood methods, for parameter estimation and hypothesis testing. A general model is then described that allows for several familial sources of environmental variation, assortative mating, and both major gene and polygenic effects; and an algorithm for calculating the likelihood of a pedigree under this model is indicated. Finally, some of the remaining problems in this area of biometric analysis are pointed out.     

Likelihoods of multilocus DNA fingerprints in extended families.

A concept for the application of complex pedigree analysis to multilocus DNA fingerprinting is described. By following this approach, the extent to which the DNA fingerprints of grandparents influence the phenotype likelihoods of their offspring was determined. It was demonstrated by simulation that approximately 90% of paternity disputes can be solved if mother, child, and paternal grandparents, instead of the putative father, are tested. If only phenotype information on a single paternal sib is allowed for, true paternity will be detected with reasonable persuasive power in up to 64% of cases. Exclusion of false paternity remains possible for 40% of cases. Finally, the analysis concept is modified by reducing the number of genotype variations considered in likelihood computations. This time-saving procedure is shown to yield sufficiently accurate likelihoods in the analysis of both simulation data and multilocus DNA fingerprints obtained in two large families.     

Stable and invariant adjusted directed likelihoods

For the purpose of making inferences for a one-dimensional interestparameter, or constructing approximate complementary ancillariesor residuals, the directed likelihood or signed square rootof the likelihood ratio statistic can be adjusted so that theresulting modified directed likelihood is under ordinary repeatedsampling approximately standard normal with error of O(n^–3/2),conditional on a suitable ancillary statistic and hence unconditionally.In general, suitable specification of the ancillary statisticmay be difficult. We introduce two adjusted directed likelihoodswhich are similar to the modified directed likelihood but donot require the specification of the ancillary statistic. Theerror of the standard normal approximation to the distributionof these new adjusted directed likelihoods is O(n^–1),conditional on any reasonable ancillary statistic, which isstill an improvement over the unadjusted directed likelihoods.     

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.     

Fast computation of genetic likelihoods on human pedigree data.

Gene mapping and genetic epidemiology require large-scale computation of likelihoods based on human pedigree data. Although computation of such likelihoods has become increasingly sophisticated, fast calculations are still impeded by complex pedigree structures, by models with many underlying loci and by missing observations on key family members. The current paper 'introduces' a new method of array factorization that substantially accelerates linkage calculations with large numbers of markers. This method is not limited to nuclear families or to families with complete phenotyping. Vectorization and parallelization are two general-purpose hardware techniques for accelerating computations. These techniques can assist in the rapid calculation of genetic likelihoods. We describe our experience using both of these methods with the existing program MENDEL. A vectorized version of MENDEL was run on an IBM 3090 supercomputer. A parallelized version of MENDEL was run on parallel machines of different architectures and on a network of workstations. Applying these revised versions of MENDEL to two challenging linkage problems yields substantial improvements in computational speed.     

A note on Cannings and Thompson''s sequential sampling scheme for pedigrees.

We consider sequential sampling of pedigrees for genetic analysis. Cannings and Thompson (1977) gave simple, general guidelines for valid sequential sampling schemes. We show that their formulation of the likelihood contains an error, which is, however, easily corrected so as to maintain the validity of the sequential scheme. We also point out that although sequential and fixed-structure pedigree sampling do have the same likelihoods (as Cannings and Thompson showed), and therefore yield the same maximum likelihood point estimates of genetic parameters, they do not necessarily yield the same significance tests or confidence intervals.     

Pedigree reconstruction from SNP data: parentage assignment,sibship clustering and beyond

Data on hundreds or thousands of single nucleotide polymorphisms (SNPs) provide detailed information about the relationships between individuals, but currently few tools can turn this information into a multigenerational pedigree. I present the r package sequoia , which assigns parents, clusters half‐siblings sharing an unsampled parent and assigns grandparents to half‐sibships. Assignments are made after consideration of the likelihoods of all possible first‐, second‐ and third‐degree relationships between the focal individuals, as well as the traditional alternative of being unrelated. This careful exploration of the local likelihood surface is implemented in a fast, heuristic hill‐climbing algorithm. Distinction between the various categories of second‐degree relatives is possible when likelihoods are calculated conditional on at least one parent of each focal individual. Performance was tested on simulated data sets with realistic genotyping error rate and missingness, based on three different large pedigrees (N = 1000–2000). This included a complex pedigree with overlapping generations, occasional close inbreeding and some unknown birth years. Parentage assignment was highly accurate down to about 100 independent SNPs (error rate <0.1%) and fast (<1 min) as most pairs can be excluded from being parent–offspring based on opposite homozygosity. For full pedigree reconstruction, 40% of parents were assumed nongenotyped. Reconstruction resulted in low error rates (<0.3%), high assignment rates (>99%) in limited computation time (typically <1 h) when at least 200 independent SNPs were used. In three empirical data sets, relatedness estimated from the inferred pedigree was strongly correlated to genomic relatedness.     

Likelihood estimation of quantitative genetic parameters when selection occurs: models and problems

Conceptual aspects of estimation of genetic components of variance and covariance under selection are discussed, with special attention to likelihood methods. Certain selection processes are described and alternative likelihoods that can be used for analysis are specified. There is a mathematical relationship between the likelihoods that permits comparing the relative amount of information contained in them. Theoretical arguments and evidence indicate that point inferences made from likelihood functions are not affected by some forms of selection.     

The problem of ascertainment for linkage analysis.

It is generally believed that ascertainment corrections are unnecessary in linkage analysis, provided individuals are selected for study solely on the basis of trait phenotype and not on the basis of marker genotype. The theoretical rationale for this is that standard linkage analytic methods involve conditioning likelihoods on all the trait data, which may be viewed as an application of the ascertainment assumption-free (AAF) method of Ewens and Shute. In this paper, we show that when the observed pedigree structure depends on which relatives within a pedigree happen to have been the probands (proband-dependent, or PD, sampling) conditioning on all the trait data is not a valid application of the AAF method and will result in asymptotically biased estimates of genetic parameters (except under single ascertainment). Furthermore, this result holds even if the recombination fraction R is the only parameter of interest. Since the lod score is proportional to the likelihood of the marker data conditional on all the trait data, this means that when data are obtained under PD sampling the lod score will yield asymptotically biased estimates of R, and that so-called mod scores (i.e., lod scores maximized over both R and parameters theta of the trait distribution) will yield asymptotically biased estimates of R and theta. Furthermore, the problem appears to be intractable, in the sense that it is not possible to formulate the correct likelihood conditional on observed pedigree structure. In this paper we do not investigate the numerical magnitude of the bias, which may be small in many situations. On the other hand, virtually all linkage data sets are collected under PD sampling. Thus, the existence of this bias will be the rule rather than the exception in the usual applications.