Hot RAD: A Tool for Analysis of Next-Gen RAD Tag Data

Hot RAD: A Tool for Analysis of Next-Gen RAD Tag Data
Lauren A. Assour, Nicholas LaRosa, Scott J. Emrich

Restriction site Associated DNA (RAD) tagging (also known as RAD-seq, etc.) is an emerging method for analyzing an organism’s genome without completely sequencing it. This can be applied to a non-model organism without a reference genome, though this creates the problem of how to begin data analysis on unmapped and unannotated reads. Our program, Hot RAD, presents a straightforward and easy-to-use method to take raw Illumina data that has been RAD tagged and produce consensus contigs or sequence stacks using a distributed framework, creating a basis on which to begin analyzing an organism’s DNA. The GUI (graphical user interface) element of our tool makes it easy for those not familiar with the command line to take raw sequence files and produce usable data in a timely manner.

Calculating the Unrooted Subtree Prune-and-Regraft Distance

Calculating the Unrooted Subtree Prune-and-Regraft Distance
Chris Whidden, Frederick A. Matsen IV

The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be computed relatively efficiently between rooted trees using fixed-parameter-tractable maximum agreement forest (MAF) algorithms, no MAF formulation is known for the unrooted case. Correspondingly, previous algorithms are unable to compute unrooted SPR distances larger than 7.
In this paper, we substantially advance understanding of and computational algorithms for the unrooted SPR distance. First we identify four properties of minimal SPR paths, each of which suggests that no MAF formulation exists in the unrooted case. We then prove the 2008 conjecture of Hickey et al. that chain reduction preserves the unrooted SPR distance. This reduces the problem to a linear size problem kernel, substantially improving on the previous best quadratic size kernel. Then we introduce a new lower bound on the unrooted SPR distance called the replug distance that is amenable to MAF methods, and give an efficient fixed-parameter algorithm for calculating it. Finally, we develop a “progressive A*” search algorithm using multiple heuristics, including the TBR and replug distances, to exactly compute the unrooted SPR distance. Our algorithm is nearly two orders of magnitude faster than previous methods on small trees, and allows computation of unrooted SPR distances as large as 14 on trees with 50 leaves.

MetaScope – Fast and accurate identification of microbes in metagenomic sequencing data

MetaScope – Fast and accurate identification of microbes in metagenomic sequencing data
Benjamin Buchfink, Daniel H. Huson, Chao Xie

MetaScope is a fast and accurate tool for analyzing (host-associated) metagenome datasets. Sequence alignment of reads against the host genome (if requested) and against microbial Genbank is performed using a new DNA aligner called SASS. The output of SASS is processed so as to assign all microbial reads to taxa and genes, using a new weighted version of the LCA algorithm. MetaScope is the winner of the 2013 DTRA software challenge entitled “Identify Organisms from a Stream of DNA Sequences”.

Author Post: Natural selection reduces linked neutral divergence between distantly related species

This is a guest post by Tanya Phung on her recent preprint Natural selection reduces linked neutral divergence between distantly related species

Our recent paper on natural selection reducing divergence between distantly related species has generated interesting discussions. I started this project just a little over a year ago as a rotation student in Kirk Lohmueller’s lab at UCLA. I am now a full-time member in Kirk’s group and a 2nd year Ph.D. student in the Bioinformatics program.

This project began when, in 2011, Kirk published a paper that documented signatures of natural selection affecting genetic variation at neutral sites across the human genome (Lohmueller et al., 2011). In that paper, among other things, he found a positive correlation between human-chimp divergence and recombination. This correlation is indicative of selection at linked neutral sites affecting divergence, mutagenic recombination, or possibly biased gene conversion. Based on the results of forward simulations, he concluded that background selection can drive much of this correlation. After publishing the paper, Kirk looked at divergence between humans and more distantly related species. Surprising to him, he also observed a positive correlation between human-mouse neutral divergence and recombination. This signal was unexpected. It was already shown in Birky and Walsh (1988) that selection does not affect substitution at linked neutral sites, and Kirk was carefully filtering out sites that are thought to be under direct effects of selection. Consequently, if selection was driving the correlation, it would have to be by patterns of polymorphism in the human-mouse ancestor which existed long ago. Thus, he thought there shouldn’t be any remaining signal. Kirk did not have time to follow-up this finding until a few years later when I showed up as a rotation student in his group in the Fall of 2014. While he suggested three different ideas as potential rotation projects, investigating how natural selection has affected divergence stood out to me in particular. As I read his 2011 paper and followed the references within, I was intrigued by conflicting reports in the literature about whether divergence showed a correlation with recombination and the mechanism for this potential correlation. Therefore, I set out to investigate this problem.

By the end of the rotation, I replicated what Kirk found earlier: a positive correlation between recombination and divergence in both closely and distantly related species. Then, using a coalescent simulation approach, I showed that simulations incorporating background selection in the ancestral population could recapitulate the correlation between neutral divergence and recombination observed in the empirical data.

My results indicated that natural selection could affect neutral divergence even between distantly related species. We were ready to prepare a manuscript. At the time, there were a few studies coming out reporting the importance of biased gene conversion. We did a bit more thinking about how biased gene conversion could affect our empirical correlation between neutral divergence and recombination. We decided to control for the potential effect of biased gene conversion by filtering out sites that could have been affected by it by filtering the weak to strong mutations (where an A or a T mutates to a C or a G). Filtering out weak to strong differences did not significantly affect the correlation between human-chimp neutral divergence and recombination. But to our surprise, the correlation between human-mouse neutral divergence and recombination all but vanished with our most stringent filtering. This means that much of that correlation could be driven by biased gene conversion. We thought that if background selection has affected human-mouse divergence, the signal ought to be stronger at regions near genes. When we partitioned the genome into regions near genes and far from genes, the positive correlation between human-mouse divergence and recombination was restored at regions near genes (albeit more weakly than before filtering sites that could have undergone biased gene conversion).

We realized that recombination rates are transient and have probably changed throughout the course of evolution. In fact, changing recombination rates could be obscuring the correlation between recombination and divergence after removing the confounding effects of biased gene conversion. So, we wanted to look for other signatures of how natural selection reduced neutral divergence even between distantly related species. This led us to investigate the relationship between divergence and functional content (amount of coding bases and conserved non-coding sequence in each window), and between divergence and measures of background selection represented by B-values estimated in McVicker et al. (B-values measure the strength of background selection in that region of the genome; see McVicker et al., 2009). In all pairs of species considered, we found a negative correlation between neutral divergence and functional content. This means that windows that have more functional sites tend to have less divergence at the nearby putatively neutral sites. We also found a positive correlation between neutral divergence and B-values, suggesting that regions of the genome that are under greater background selection within primates are also under greater background selection in the human-mouse ancestor. Both these analyses provide empirical evidence that natural selection has reduced neutral divergence in both recently and distantly related species.

Conventional wisdom holds that ancestral polymorphism does not affect divergence when considering species with long split times (such as human and mouse). The rationale is that the split time has been long enough for many new mutations to accumulate post-split, and any signal in the ancestral population would be diluted. While our empirical and simulation results clearly indicated otherwise, we wanted to gain some theoretical intuition on why we were still seeing these correlations. This is when Christian Huber, a post-doc who joined the lab recently from Vienna, joined in. Using a two-locus model, he showed that background selection can have a strong influence on the variation in divergence between genomic regions, even when the contribution of ancestral polymorphism to total divergence is vanishingly small. The key condition is a reasonably large ancestral population size.

Now we have empirical, theoretical, and simulation results which strongly argue that background selection contributes to reducing divergence at linked neutral sites. Our results question the commonly held notion that ancestral polymorphism does not measurably affect divergence in distantly related species. Further, our results indicate the importance of background selection at shaping genetic variation across the genome. Many current popular methods to infer demographic parameters from whole genomes (e.g. PSMC, G-phos) do not take background selection into account. Our work suggests that because background selection has a large effect on the variance in coalescent times across the genome, incorporating its effects into estimates of demographic parameters should yield more accurate results.

Summary

When I started working on this project as a rotation student, I had no idea that it would turn out to address a controversy and challenge a commonly held notion in population genetics. As I transitioned from an experimental microbiologist to a population geneticist, this project has given me many opportunities to learn important concepts and theories in the field. This paper not only opens opportunities to revise methods in the field but also gives me the foundation to continue working on understanding evolutionary forces that influence genetic variation across the genome.

Birky, C.W., and Walsh, J.B. (1988). Effects of linkage on rates of molecular evolution. Proc. Natl. Acad. Sci. U. S. A. 85, 6414–6418.

Lohmueller, K.E., Albrechtsen, A., Li, Y., Kim, S.Y., Korneliussen, T., Vinckenbosch, N., Tian, G., Huerta-Sanchez, E., Feder, A.F., Grarup, N., et al. (2011). Natural Selection Affects Multiple Aspects of Genetic Variation at Putatively Neutral Sites across the Human Genome. PLoS Genet 7, e1002326.

McVicker, G., Gordon, D., Davis, C., and Green, P. (2009). Widespread genomic signatures of natural selection in hominid evolution. PLoS Genet. 5, e1000471.

Direct estimate of the spontaneous mutation rate uncovers the effects of drift and recombination in the Chlamydomonas reinhardtii plastid genome

Rob W Ness, Susanne A Kraemer, Nick Colegrave, Peter D Keightley

A statistical approach to genome size evolution: Observations and explanations

A statistical approach to genome size evolution: Observations and explanations

Dirson Jian Li

Kaiju: Fast and sensitive taxonomic classification for metagenomics

Kaiju: Fast and sensitive taxonomic classification for metagenomics

Peter Menzel, Kim Lee Ng, Anders Krogh

The State of Software in Evolutionary Biology

The State of Software in Evolutionary Biology

Diego Darriba, Tomas Flouri, Alexandros Stamatakis

Testing Rare-Variant Association without Calling Genotypes Allows for Systematic Differences in Sequencing between Cases and Controls

Testing Rare-Variant Association without Calling Genotypes Allows for Systematic Differences in Sequencing between Cases and Controls

Yi-Juan Hu, Peizhou Liao, Henry Richard Johnston, Andrew Allen, Glen Satten

Spatial selection and local adaptation jointly shape life-history evolution during range expansion

Spatial selection and local adaptation jointly shape life-history evolution during range expansion

Katrien Van Petegem, Jeroen Boeye, Robby Stoks, Dries Bonte