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.     

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.     

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.     

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.     

Finding consistent gene transmission patterns on large and complex pedigrees

A heuristic algorithm for finding gene transmission patterns on large and complex pedigrees with partially observed genotype data is proposed. The method can be used to generate an initial point for a Markov chain Monte Carlo simulation or to check that the given pedigree and the genotype data are consistent. In small pedigrees, the algorithm is exact by exhaustively enumerating all possibilities, but, in large pedigrees, with a considerable amount of unknown data, only a subset of promising configurations can actually be checked. For that purpose, the configurations are ordered by combining the approximative conditional probability distribution of the unknown genotypes with the information on the relationships between individuals. We also introduce a way to divide the task into subparts, which has been shown to be useful in large pedigrees. The algorithm has been implemented in a program called APE (Allelic Path Explorer) and tested in three different settings with good results.     

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 genotypes with independently sampled descent graphs

A method for estimating genotypic and identity-by-descent probabilities in complex pedigrees is described. The method consists of an algorithm for drawing independent genotype samples which are consistent with the pedigree and observed genotype. The probability distribution function for samples obtained using the algorithm can be evaluated up to a normalizing constant, and combined with the likelihood to produce a weight for each sample. Importance sampling is then used to estimate genotypic and identity-by-descent probabilities. On small but complex pedigrees, the genotypic probability estimates are demonstrated to be empirically unbiased. On large complex pedigrees, while the algorithm for obtaining genotype samples is feasible, importance sampling may require an infeasible number of samples to estimate genotypic probabilities with accuracy.     

Reconstructing pedigrees: a combinatorial perspective

A pedigree is a directed graph that displays the relationship between individuals according to their parentage. We derive a combinatorial result that shows how any pedigree-up to individuals who have no extant (present-day) ancestors-can be reconstructed from (sex-labelled) pedigrees that describe the ancestry of single extant individuals and pairs of extant individuals. Furthermore, this reconstruction can be done in polynomial time. We also provide an example to show that the corresponding reconstruction result does not hold for pedigrees that are not sex-labelled. We then show how any pedigree can also be reconstructed from two functions that just describe certain circuits in the pedigree. Finally, we obtain an enumeration result for pedigrees that is relevant to the question of how many segregating sites are needed to reconstruct 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.     

Detection and Integration of Genotyping Errors in Statistical Genetics

Detection of genotyping errors and integration of such errors in statistical analysis are relatively neglected topics, given their importance in gene mapping. A few inopportunely placed errors, if ignored, can tremendously affect evidence for linkage. The present study takes a fresh look at the calculation of pedigree likelihoods in the presence of genotyping error. To accommodate genotyping error, we present extensions to the Lander-Green-Kruglyak deterministic algorithm for small pedigrees and to the Markov-chain Monte Carlo stochastic algorithm for large pedigrees. These extensions can accommodate a variety of error models and refrain from simplifying assumptions, such as allowing, at most, one error per pedigree. In principle, almost any statistical genetic analysis can be performed taking errors into account, without actually correcting or deleting suspect genotypes. Three examples illustrate the possibilities. These examples make use of the full pedigree data, multiple linked markers, and a prior error model. The first example is the estimation of genotyping error rates from pedigree data. The second-and currently most useful-example is the computation of posterior mistyping probabilities. These probabilities cover both Mendelian-consistent and Mendelian-inconsistent errors. The third example is the selection of the true pedigree structure connecting a group of people from among several competing pedigree structures. Paternity testing and twin zygosity testing are typical applications.     

CoPE: a collaborative pedigree drawing environment.

SUMMARY: We developed a collaborative pedigree environment called CoPE. This environment includes a Java program for drawing pedigrees and a standardized system for pedigree storage. Unlike other existing pedigree programs, this software is particularly intended for epidemiologists in the sense that it allows customized automatic drawing of large numbers of pedigrees and remote and distributed consultation of pedigrees. AVAILABILITY: At http://www.infobiogen.fr/services/CoPE     

A sampling algorithm for segregation analysis

Methods for detecting Quantitative Trait Loci (QTL) without markers have generally used iterative peeling algorithms for determining genotype probabilities. These algorithms have considerable shortcomings in complex pedigrees. A Monte Carlo Markov chain (MCMC) method which samples the pedigree of the whole population jointly is described. Simultaneous sampling of the pedigree was achieved by sampling descent graphs using the Metropolis-Hastings algorithm. A descent graph describes the inheritance state of each allele and provides pedigrees guaranteed to be consistent with Mendelian sampling. Sampling descent graphs overcomes most, if not all, of the limitations incurred by iterative peeling algorithms. The algorithm was able to find the QTL in most of the simulated populations. However, when the QTL was not modeled or found then its effect was ascribed to the polygenic component. No QTL were detected when they were not simulated.     

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

Identifying pedigrees segregating at a major locus for a quantitative trait: an efficient strategy for linkage analysis

Having found evidence for segregation at a major locus for a quantitative trait, a logical next step is to identify those pedigrees in which major-locus segregation is occurring. If the quantitative trait is a risk factor for an associated disease, identifying such segregating pedigrees can be important in classifying families by etiology, in risk assessment, and in suggesting treatment modalities. Identifying segregating pedigrees can also be helpful in selecting pedigrees to include in a subsequent linkage study to map the major locus. Here, we describe a strategy to identify pedigrees segregating at a major locus for a quantitative trait. We apply this pedigree selection strategy to simulated data generated under a major-locus or mixed model with a rare dominant allele and sampled according to one of several fixed-structure or sequential sampling designs. We demonstrate that for the situations considered, the pedigree selection strategy is sensitive and specific and that a linkage study based only on the pedigrees classified as segregating extracts essentially all the linkage information in the entire sample of pedigrees. Our results suggest that for large-scale linkage studies involving many genetic markers, the savings from this strategy can be substantial and that, compared with fixed-structure sampling, sequential sampling of pedigrees can greatly improve the efficiency for linkage analysis of a quantitative trait.     

The Elston-Stewart algorithm for continuous genotypes and environmental factors.

The Elston-Stewart algorithm for a normally distributed trait under a polygenic model is explained in detail and extended to allow for other continuous environmental variables. This formulation is especially useful for large pedigrees, as it avoids the need to invert matrices. Whereas it may not be feasible by this method to estimate all the various components of previously suggested models for polygenic inheritance, it can allow for a reasonably flexible pedigree correlational structure under which valid tests can be performed for fixed effects that may affect the phenotype.     

Handling marker-marker linkage disequilibrium: pedigree analysis with clustered markers

Single-nucleotide polymorphisms (SNPs) are rapidly replacing microsatellites as the markers of choice for genetic linkage studies and many other studies of human pedigrees. Here, we describe an efficient approach for modeling linkage disequilibrium (LD) between markers during multipoint analysis of human pedigrees. Using a gene-counting algorithm suitable for pedigree data, our approach enables rapid estimation of allele and haplotype frequencies within clusters of tightly linked markers. In addition, with the use of a hidden Markov model, our approach allows for multipoint pedigree analysis with large numbers of SNP markers organized into clusters of markers in LD. Simulation results show that our approach resolves previously described biases in multipoint linkage analysis with SNPs that are in LD. An updated version of the freely available Merlin software package uses the approach described here to perform many common pedigree analyses, including haplotyping and haplotype frequency estimation, parametric and nonparametric multipoint linkage analysis of discrete traits, variance-components and regression-based analysis of quantitative traits, calculation of identity-by-descent or kinship coefficients, and case selection for follow-up association studies. To illustrate the possibilities, we examine a data set that provides evidence of linkage of psoriasis to chromosome 17.     

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

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

Clinical evaluation and mitochondrial DNA sequence analysis in two Chinese families with aminoglycoside-induced and non-syndromic hearing loss

We report here the clinical, genetic, and molecular characterization of two Chinese pedigrees with aminoglycoside-induced and non-syndromic hearing impairment. Clinical evaluation revealed the variable phenotype of hearing impairment including audiometric configuration in these subjects. Penetrances of hearing loss in BJ105 and BJ106 pedigrees are 67% and 33%, respectively. In particular, three of 10 affected matrilineal relatives of BJ105 pedigree had aminoglycoside-induced hearing loss, while seven affected matrilineal relatives in BJ105 pedigree and six affected matrilineal relatives in BJ106 pedigree did not have a history of exposure to aminoglycosides. Sequence analysis of the complete mitochondrial genomes in these pedigrees showed the identical homoplasmic A1555G mutation and distinct sets of mtDNA variants belonging to haplogroups F3 and M7b. These variants showed no evolutionary conservation, implying that mitochondrial haplotype may not play a significant role in the phenotypic expression of the A1555G mutation in these Chinese pedigrees. However, aminoglycosides and nuclear backgrounds appear to be major modifier factors for the phenotypic manifestation of the A1555G mutation in these Chinese families.