Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations

Nucleotide sequence diversity of floral pigment genes in Mexican populations of Ipomoea purpurea (morning glory) accord with a neutral model of evolution

The common morning glory (Ipomoea purpurea) is an annual vine native to Central and Southern Mexico. The genetics of flower color polymorphisms and interactions with the biotic environment have been extensively studied in I. purpurea and in its sister species I. nil. In this study, we examine nucleotide sequence polymorphism in 11 loci, 9 of which are known to participate in a pathway that produces floral pigments. A sample of 30 I. purpurea accessions from the native range of Central and Southern Mexico comprise the data, along with one accession from each of the two sister species I. alba and I. nil. We observe moderate levels of nucleotide sequence polymorphism of ~1%. The ratio of recombination to mutation parameter estimates (ρ/θ) of ~2.5 appears consistent with a mixed-mating system. Ipomoea resequencing data from these genic regions are noteworthy in providing a good fit to the standard neutral model of molecular evolution. The derived silent site frequency spectrum is very close to that predicted by coalescent simulations of a drift-mutation process, and Tajima's D values are not significantly different from expectations under neutrality.

New methods for inference of local tree topologies with recombinant SNP sequences in populations

Large amount of population-scale genetic variation data are being collected in populations. One potentially important biological problem is to infer the population genealogical history from these genetic variation data. Partly due to recombination, genealogical history of a set of DNA sequences in a population usually cannot be represented by a single tree. Instead, genealogy is better represented by a genealogical network, which is a compact representation of a set of correlated local genealogical trees, each for a short region of genome and possibly with different topology. Inference of genealogical history for a set of DNA sequences under recombination has many potential applications, including association mapping of complex diseases. In this paper, we present two new methods for reconstructing local tree topologies with the presence of recombination, which extend and improve the previous work in. We first show that the "tree scan" method can be converted to a probabilistic inference method based on a hidden Markov model. We then focus on developing a novel local tree inference method called RENT that is both accurate and scalable to larger data. Through simulation, we demonstrate the usefulness of our methods by showing that the hidden-Markov-model-based method is comparable with the original method in terms of accuracy. We also show that RENT is competitive with other methods in terms of inference accuracy, and its inference error rate is often lower and can handle large data.

Algorithms to distinguish the role of gene-conversion from single-crossover recombination in the derivation of SNP sequences in populations

Meiotic recombination is a fundamental biological event and one of the principal evolutionary forces responsible for shaping genetic variation within species. In addition to its fundamental role, recombination is central to several critical applied problems. The most important example is "association mapping" in populations, which is widely hoped to help find genes that influence genetic diseases (Carlson et al., 2004; Clark, 2003). Hence, a great deal of recent attention has focused on problems of inferring the historical derivation of sequences in populations when both mutations and recombinations have occurred. In the algorithms literature, most of that recent work has been directed to single-crossover recombination. However, gene-conversion is an important, and more common, form of (two-crossover) recombination which has been much less investigated in the algorithms literature. In this paper, we explicitly incorporate gene-conversion into discrete methods to study historical recombination. We are concerned with algorithms for identifying and locating the extent of historical crossing-over and gene-conversion (along with single-nucleotide mutation), and problems of constructing full putative histories of those events. The novel technical issues concern the incorporation of gene-conversion into recently developed discrete methods (Myers and Griffiths, 2003; Song et al., 2005) that compute lower and upper-bound information on the amount of needed recombination without gene-conversion. We first examine the most natural extension of the lower bound methods from Myers and Griffiths (2003), showing that the extension can be computed efficiently, but that this extension can only yield weak lower bounds. We then develop additional ideas that lead to higher lower bounds, and show how to solve, via integer-linear programming, a more biologically realistic version of the lower bound problem. We also show how to compute effective upper bounds on the number of needed single-crossovers and gene-conversions, along with explicit networks showing a putative history of mutations, single-crossovers and gene-conversions. Both lower and upper bound methods can handle data with missing entries, and the upper bound method can be used to infer missing entries with high accuracy. We validate the significance of these methods by showing that they can be effectively used to distinguish simulation-derived sequences generated without gene-conversion from sequences that were generated with gene-conversion. We apply the methods to recently studied sequences of Arabidopsis thaliana, identifying many more regions in the sequences than were previously identified (Plagnol et al., 2006), where gene-conversion may have played a significant role. Demonstration software is available at www.csif.cs.ucdavis.edu/~gusfield.

Molecular population genetics of Drosophila subtelomeric DNA

DNA sequence surveys in yeast and humans suggest that the forces shaping telomeric polymorphism and divergence are distinctly more dynamic than those in the euchromatic, gene-rich regions of the chromosomes. However, the generality of this pattern across outbreeding, multicellular eukaryotes has not been determined. To characterize the structure and evolution of Drosophila telomeres, we collected and analyzed molecular population genetics data from the X chromosome subtelomere in 58 lines of North American Drosophila melanogaster and 29 lines of African D. melanogaster. We found that Drosophila subtelomeres exhibit high levels of both structural and substitutional polymorphism relative to linked euchromatic regions. We also observed strikingly different patterns of variation in the North American and African samples. Moreover, our analyses of the polymorphism data identify a localized hotspot of recombination in the most-distal portion of the X subtelomere. While the levels of polymorphism decline sharply and in parallel with rates of crossing over per physical length over the distal first euchromatic megabase pairs of the X chromosome, our data suggest that they rise again sharply in the subtelomeric region (approximately 80 kbp). These patterns of historical recombination and geographic differentiation indicate that, similar to yeast and humans, Drosophila subtelomeric DNA is evolving very differently from euchromatic DNA.

A decomposition theory for phylogenetic networks and incompatible characters

Phylogenetic networks are models of evolution that go beyond trees, incorporating non-tree-like biological events such as recombination (or more generally reticulation), which occur either in a single species (meiotic recombination) or between species (reticulation due to lateral gene transfer and hybrid speciation). The central algorithmic problems are to reconstruct a plausible history of mutations and non-tree-like events, or to determine the minimum number of such events needed to derive a given set of binary sequences, allowing one mutation per site. Meiotic recombination, reticulation and recurrent mutation can cause conflict or incompatibility between pairs of sites (or characters) of the input. Previously, we used "conflict graphs" and "incompatibility graphs" to compute lower bounds on the minimum number of recombination nodes needed, and to efficiently solve constrained cases of the minimization problem. Those results exposed the structural and algorithmic importance of the non-trivial connected components of those two graphs. In this paper, we more fully develop the structural importance of non-trivial connected components of the incompatibility and conflict graphs, proving a general decomposition theorem (Gusfield and Bansal, 2005) for phylogenetic networks. The decomposition theorem depends only on the incompatibilities in the input sequences, and hence applies to many types of phylogenetic networks, and to any biological phenomena that causes pairwise incompatibilities. More generally, the proof of the decomposition theorem exposes a maximal embedded tree structure that exists in the network when the sequences cannot be derived on a perfect phylogenetic tree. This extends the theory of perfect phylogeny in a natural and important way. The proof is constructive and leads to a polynomial-time algorithm to find the unique underlying maximal tree structure. We next examine and fully solve the major open question from Gusfield and Bansal (2005): Is it true that for every input there must be a fully decomposed phylogenetic network that minimizes the number of recombination nodes used, over all phylogenetic networks for the input. We previously conjectured that the answer is yes. In this paper, we show that the answer in is no, both for the case that only single-crossover recombination is allowed, and also for the case that unbounded multiple-crossover recombination is allowed. The latter case also resolves a conjecture recently stated in (Huson and Klopper, 2007) in the context of reticulation networks. Although the conjecture from Gusfield and Bansal (2005) is disproved in general, we show that the answer to the conjecture is yes in several natural special cases, and establish necessary combinatorial structure that counterexamples to the conjecture must possess. We also show that counterexamples to the conjecture are rare (for the case of single-crossover recombination) in simulated data.