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.     

Modeling the effect of inbreeding among founders in linkage analysis

In this paper, we present a unified mathematical model for linkage analysis that allows for inbreeding among founders in all families. The identical by descent (IBD) configuration of each pedigree is modeled as a Markov process containing two parameters; the inverse inbreeding and kinship coefficient and a rate parameter proportional to the inverse expected length of chromosome segments shared IBD by two different founder haplotypes. We use hidden Markov models and define a forward-backward algorithm for computing the conditional IBD-distribution given marker data, thereby extending the multipoint method of Lander and Green [1987. Construction of multilocus genetic maps in humans, Proc. Natl. Acad. Sci. USA 84, 2363-2367] to situations where founders are inbred. Our methodology is valid for arbitrary pedigree structures. Simulation and theoretical approximations for nonparametric linkage (NPL) analysis based on affected sib pairs reveal that NPL scores are inflated and type 1 errors increased when the inbreeding coefficient or rate parameter is underestimated. When the parents are genotyped, we present a general way of modifying the score function to drastically reduce this effect.     

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.     

Allelic Richness following Population Founding Events – A Stochastic Modeling Framework Incorporating Gene Flow and Genetic Drift

Allelic richness (number of alleles) is a measure of genetic diversity indicative of a population''s long-term potential for adaptability and persistence. It is used less commonly than heterozygosity as a genetic diversity measure, partially because it is more mathematically difficult to take into account the stochastic process of genetic drift for allelic richness. This paper presents a stochastic model for the allelic richness of a newly founded population experiencing genetic drift and gene flow. The model follows the dynamics of alleles lost during the founder event and simulates the effect of gene flow on maintenance and recovery of allelic richness. The probability of an allele''s presence in the population was identified as the relevant statistical property for a meaningful interpretation of allelic richness. A method is discussed that combines the probability of allele presence with a population''s allele frequency spectrum to provide predictions for allele recovery. The model''s analysis provides insights into the dynamics of allelic richness following a founder event, taking into account gene flow and the allele frequency spectrum. Furthermore, the model indicates that the “One Migrant per Generation” rule, a commonly used conservation guideline related to heterozygosity, may be inadequate for addressing preservation of diversity at the allelic level. This highlights the importance of distinguishing between heterozygosity and allelic richness as measures of genetic diversity, since focusing merely on the preservation of heterozygosity might not be enough to adequately preserve allelic richness, which is crucial for species persistence and evolution.     

Microsatellite diversity, pedigree relatedness and the contributions of founder lineages to thoroughbred horses

The thoroughbred (TB) horse is one of the oldest breeds of domestic animals, with pedigree records spanning three centuries. Because the population is essentially closed, there is concern about loss of genetic variation. Here we report two parallel analyses. In the first, genetic variation in the current population is measured using data from 13 microsatellite loci in 211 horses with relationships calculated based on allele sharing. In the second analysis, pedigree information is used to calculate genetic relationships between animals based on shared ancestry. These two measures of relationship are compared and shown to be closely related. Together, they provide an estimate of the amount of genetic variation which existed in founder animals. This study confirms the narrow genetic base of the breed and provides comprehensive analysis of contributions of founder animals. Seventy-eight percent of alleles in the current population are derived from 30 founders, 27 of these male. Ten founder females account for 72% of maternal lineages, while one founder stallion is responsible for 95% of paternal lineages.     

Gene extinction and allelic origins in complex genealogies

With the increasing emphasis on data analysis in mathematical genetics, problems of parametrizing genealogical structure become of practical importance. A complete specification of the genetic effects of genealogical structure is provided by the probabilities of genetically distinct states of gene identity by descent. Although this provides a direct parametrization for the joint distribution of traits on a set of related individuals, it is an unwieldy tool in the analysis of large and complex genealogies. Probabilities of joint descent of founder genes and likely ancestries of alleles provide alternative characterizations of relationship and have direct application in practical problems. Joint extinction probabilities of founder genes can also be derived as ancestral likelihoods: evolutionarily, the most significant characteristic of a genealogical structure must be its effect on the survival and extinction of genes.     

Genome sharing in large pedigrees: multiple imputation of ibd for linkage detection

Our objective is the development of robust methods for assessment of evidence for linkage of loci affecting a complex trait to a marker linkage group, using data on extended pedigrees. Using Markov chain Monte Carlo (MCMC) methods, it is possible to sample realizations from the distribution of gene identity by descent (IBD) patterns on a pedigree, conditional on observed data YM at multiple marker loci. Measures of gene IBDW which capture joint genome sharing in extended pedigrees often have unknown and highly skewed distributions, particularly when conditioned on marker data. MCMC provides a direct estimate of the distribution of such measures. Let W be the IBD measure from data YM, and W* the IBD measure from pseudo-data Y*M simulated with the same data availability and genetic marker model as the true data YM, but in the absence of linkage. Then measures of the difference in distributions of W and W* provide evidence for linkage. This approach extracts more information from the data YM than either comparison to the pedigree prior distribution of W or use of statistics that are expectations of W given the data YM. A small example is presented.     

QTL analysis in arbitrary pedigrees with incomplete marker information

Mapping quantitative trait loci (QTL) in arbitrary outbred pedigrees is complicated by the combinatorial possibilities of allele flow relationships and of the founder allelic configurations. Exact methods are only available for rather short and simple pedigrees. Stochastic simulation using Markov chain Monte Carlo (MCMC) integration offers more flexibility. MCMC methods are less natural in a frequentist than in a Bayesian context, which we therefore adopt. Among the MCMC algorithms for updating marker locus genotypes, we implement the descent-graph algorithm. It can be used to update marker locus allele flow relationships and can handle arbitrarily complex pedigrees and missing marker information. Compared with updating marker genotypic information, updating QTL parameters, such as position, effects, and the allele flow relationships is relatively easy with MCMC. We treat the effect of each diploid combination of founder alleles as a random variable and only estimate the variance of these effects, ie, we model diploid genotypic effects instead of the usual partition in additive and dominance effects. This is a variant of the random model approach. The number of QTL alleles is generally unknown. In the Bayesian context, the number of QTL present on a linkage group can be treated as variable. Computer simulations suggest that the algorithm can indeed handle complex pedigrees and detect two QTL on a linkage group, but that the number of individuals in a single extended family is limited to about 50 to 100 individuals.     

On reducing the statespace of hidden Markov models for the identity by descent process

Important methods for calculating likelihoods of genealogical relationships and mapping genes are based on hidden Markov models for the process of identity by descent along chromosomes. The computational time for the algorithms depends critically on the size of the statespace of the hidden Markov model. We describe the maximal grouping together of states of the model to reduce the size of the statespace. This grouping is based on pedigree symmetries. We also present an efficient algorithm for finding the maximal grouping.     

Bayesian restoration of a hidden Markov chain with applications to DNA sequencing.

Hidden Markov models (HMMs) are a class of stochastic models that have proven to be powerful tools for the analysis of molecular sequence data. A hidden Markov model can be viewed as a black box that generates sequences of observations. The unobservable internal state of the box is stochastic and is determined by a finite state Markov chain. The observable output is stochastic with distribution determined by the state of the hidden Markov chain. We present a Bayesian solution to the problem of restoring the sequence of states visited by the hidden Markov chain from a given sequence of observed outputs. Our approach is based on a Monte Carlo Markov chain algorithm that allows us to draw samples from the full posterior distribution of the hidden Markov chain paths. The problem of estimating the probability of individual paths and the associated Monte Carlo error of these estimates is addressed. The method is illustrated by considering a problem of DNA sequence multiple alignment. The special structure for the hidden Markov model used in the sequence alignment problem is considered in detail. In conclusion, we discuss certain interesting aspects of biological sequence alignments that become accessible through the Bayesian approach to HMM restoration.     

Finding noncommunicating sets for Markov chain Monte Carlo estimations on pedigrees.

Markov chain Monte Carlo (MCMC) has recently gained use as a method of estimating required probability and likelihood functions in pedigree analysis, when exact computation is impractical. However, when a multiallelic locus is involved, irreducibility of the constructed Markov chain, an essential requirement of the MCMC method, may fail. Solutions proposed by several researchers, which do not identify all the noncommunicating sets of genotypic configurations, are inefficient with highly polymorphic loci. This is a particularly serious problem in linkage analysis, because highly polymorphic markers are much more informative and thus are preferred. In the present paper, we describe an algorithm that finds all the noncommunicating classes of genotypic configurations on any pedigree. This leads to a more efficient method of defining an irreducible Markov chain. Examples, including a pedigree from a genetic study of familial Alzheimer disease, are used to illustrate how the algorithm works and how penetrances are modified for specific individuals to ensure irreducibility.     

Impact on Reindeer (Rangifer tarandus) Genetic Diversity from Two Parallel Population Bottlenecks Founded from a Common Source

Population bottlenecks and founder events reduce genetic diversity through stochastic processes associated with the sampling of alleles at the time of the bottleneck, and the recombination of alleles that are identical by descent. At the same time bottlenecks and founder events can structure populations through the stochastic distortion of allele frequencies. Here we undertake an empirical assessment of the impact of two independent bottlenecks of known size from a known source, and consider inference about evolutionary process in the context of simulations and theoretical expectations. We find a similar level of reduced variation in the parallel bottleneck events, with the greater impact on the population that began with the smaller number of females. The level of diversity remaining was consistent with model predictions, but only if re-growth of the population was essentially exponential and polygeny was minimal at the early stages. There was a high level of differentiation seen compared to the source population and between the two bottlenecked populations, reflecting the stochastic distortion of allele frequencies. We provide empirical support for the theoretical expectations that considerable diversity can remain following a severe bottleneck event, given rapid demographic recovery, and that populations founded from the same source can become quickly differentiated. These processes may be important during the evolution of population genetic structure for species affected by rapid changes in available habitat.     

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.     

A Full Bayesian Approach for Boolean Genetic Network Inference

Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data.     

Computation of identity by descent probabilities conditional on DNA markers via a Monte Carlo Markov Chain method

The accurate estimation of the probability of identity by descent (IBD) at loci or genome positions of interest is paramount to the genetic study of quantitative and disease resistance traits. We present a Monte Carlo Markov Chain method to compute IBD probabilities between individuals conditional on DNA markers and on pedigree information. The IBDs can be obtained in a completely general pedigree at any genome position of interest, and all marker and pedigree information available is used. The method can be split into two steps at each iteration. First, phases are sampled using current genotypic configurations of relatives and second, crossover events are simulated conditional on phases. Internal track is kept of all founder origins and crossovers such that the IBD probabilities averaged over replicates are rapidly obtained. We illustrate the method with some examples. First, we show that all pedigree information should be used to obtain line origin probabilities in F2 crosses. Second, the distribution of genetic relationships between half and full sibs is analysed in both simulated data and in real data from an F2 cross in pigs.     

Whole-genome QTL analysis for MAGIC

Key message

An efficient whole genome method of QTL analysis is presented for Multi-parent advanced generation integrated crosses.

Abstract

Multi-parent advanced generation inter-cross (MAGIC) populations have been developed for mice and several plant species and are useful for the genetic dissection of complex traits. The analysis of quantitative trait loci (QTL) in these populations presents some additional challenges compared with traditional mapping approaches. In particular, pedigree and marker information need to be integrated and founder genetic data needs to be incorporated into the analysis. Here, we present a method for QTL analysis that utilizes the probability of inheriting founder alleles across the whole genome simultaneously, either for intervals or markers. The probabilities can be found using three-point or Hidden Markov Model (HMM) methods. This whole-genome approach is evaluated in a simulation study and it is shown to be a powerful method of analysis. The HMM probabilities lead to low rates of false positives and low bias of estimated QTL effect sizes. An implementation of the approach is available as an R package. In addition, we illustrate the approach using a bread wheat MAGIC population.     

Irreducibility and efficiency of ESIP to sample marker genotypes in large pedigrees with loops

Markov chain Monte Carlo (MCMC) methods have been proposed to overcome computational problems in linkage and segregation analyses. This approach involves sampling genotypes at the marker and trait loci. Among MCMC methods, scalar-Gibbs is the easiest to implement, and it is used in genetics. However, the Markov chain that corresponds to scalar-Gibbs may not be irreducible when the marker locus has more than two alleles, and even when the chain is irreducible, mixing has been observed to be slow. Joint sampling of genotypes has been proposed as a strategy to overcome these problems. An algorithm that combines the Elston-Stewart algorithm and iterative peeling (ESIP sampler) to sample genotypes jointly from the entire pedigree is used in this study. Here, it is shown that the ESIP sampler yields an irreducible Markov chain, regardless of the number of alleles at a locus. Further, results obtained by ESIP sampler are compared with other methods in the literature. Of the methods that are guaranteed to be irreducible, ESIP was the most efficient.     

Markov chain Monte Carlo segregation and linkage analysis for oligogenic models.

A new method for segregation and linkage analysis, with pedigree data, is described. Reversible jump Markov chain Monte Carlo methods are used to implement a sampling scheme in which the Markov chain can jump between parameter subspaces corresponding to models with different numbers of quantitative-trait loci (QTL's). Joint estimation of QTL number, position, and effects is possible, avoiding the problems that can arise from misspecification of the number of QTL's in a linkage analysis. The method is illustrated by use of a data set simulated for the 9th Genetic Analysis Workshop; this data set had several oligogenic traits, generated by use of a 1,497-member pedigree. The mixing characteristics of the method appear to be good, and the method correctly recovers the simulated model from the test data set. The approach appears to have great potential both for robust linkage analysis and for the answering of more general questions regarding the genetic control of complex traits.     

基于SSR标记的寒地水稻品种骨干亲本分析

富士光、藤系138、上育397和五优稻1是20世纪90年代至今寒地水稻品种选育的骨干亲本。利用50对SSR引物对上述骨干亲本及其衍生品种进行聚类分析和主坐标分析(principal coordinate analysis, PCO),结果表明,50对SSR引物在51份供试材料中共检测到150个等位基因,变化范围为2~6个,平均为3个;引物PIC的变化范围为0.0725~ 0.6845,平均0.3655;聚类分析将51份材料分为4类,4个骨干亲本分别被聚到4类中;PCO分析显示,四个骨干亲本相距较远,呈独立的分支,衍生品种围绕着骨干亲本分布;在检测出的39个稀有等位基因中,仅有3个存在骨干亲本中。表明近年寒地水稻品种遗传改良是围绕少数骨干亲本进行的,骨干亲本将大部分优良基因传递到了衍生品种中,SSR分析和PCO分析与系谱分析得到了一致的结果。     

Extending pedigree analysis for uncertain parentage and diverse breeding systems

Breeding programs aimed at conserving genetic diversity in populations of wildlife or rare domestic breeds rely on detailed pedigree analysis for selection of breeders that will minimize the loss of alleles, reduce the accumulation of inbreeding, and maintain gene diversity. Commonly, techniques use a matrix of kinship coefficients to derive measures of genetic variation, inbreeding, and the value of individuals as breeders. Although these techniques were first developed for use on known pedigrees of diploid individuals, the concepts and methods can be extended to apply to any entity that contains genes derived from definable sources (e.g., individual parents, social groups, colonies, gene banks) via a definable mechanism of heredity (e.g., sexual reproduction between separate sexes, hermaphroditic selfing, autozygous production of homozygous or haploid offspring, cloning). Individuals with partly unknown ancestry or multiple possible parents can also be incorporated into kinship calculations, based on probabilistic assignment of parental contributions. This paper presents the algorithms used in new PMx software to extend traditional pedigree analysis techniques used for complete pedigrees of sexually reproducing, diploid species to deal with missing information due to unknown or uncertain parentage, and other breeding systems such as clones, selfing hermaphrodites, and haploid offspring or autogamy.