A maximum pseudo-likelihood approach for estimating species trees under the coalescent model

Background  

Several phylogenetic approaches have been developed to estimate species trees from collections of gene trees. However, maximum likelihood approaches for estimating species trees under the coalescent model are limited. Although the likelihood of a species tree under the multispecies coalescent model has already been derived by Rannala and Yang, it can be shown that the maximum likelihood estimate (MLE) of the species tree (topology, branch lengths, and population sizes) from gene trees under this formula does not exist. In this paper, we develop a pseudo-likelihood function of the species tree to obtain maximum pseudo-likelihood estimates (MPE) of species trees, with branch lengths of the species tree in coalescent units.     

A comparison of common programming languages used in bioinformatics

Background  

The performance of different programming languages has previously been benchmarked using abstract mathematical algorithms, but not using standard bioinformatics algorithms. We compared the memory usage and speed of execution for three standard bioinformatics methods, implemented in programs using one of six different programming languages. Programs for the Sellers algorithm, the Neighbor-Joining tree construction algorithm and an algorithm for parsing BLAST file outputs were implemented in C, C++, C#, Java, Perl and Python.     

Comparing sequences without using alignments: application to HIV/SIV subtyping

Background  

In general, the construction of trees is based on sequence alignments. This procedure, however, leads to loss of informationwhen parts of sequence alignments (for instance ambiguous regions) are deleted before tree building. To overcome this difficulty, one of us previously introduced a new and rapid algorithm that calculates dissimilarity matrices between sequences without preliminary alignment.     

Analysing Betula litwinowii encroachment and reforestation in the Kazbegi region,Greater Caucasus,Georgia

Aims

The encroachment of tree and shrub species in high mountains is an increasing worldwide phenomenon, which is expected to dramatically alter high‐mountain ecosystems and their functioning. Moreover it indicates in some cases a reforestation process, which will result in important ecological and social benefits, including carbon sequestration and protection against landslides. We therefore examined the spatial extent of forest growth and shrub encroachment mainly of birch (Betula litwinowii) in the sub‐alpine belt of the Central Greater Caucasus between 1987 and 2010 and its relation to topographic site conditions.

Location

Kazbegi district, Central Greater Caucasus, Georgia.

Methods

We analysed 155 vegetation relevés sampled in 2009, 2011 and 2015, mainly derived from the Caucasus Vegetation Database, to obtain information about topographic site conditions and structure of B. litwinowii stands. B. litwinowii forest growth was assessed by digitizing the forest outlines from aerial and space‐borne imagery (1987, 2005 and 2010). To identify areas of B. litwinowii encroachment as an indicator for different encroachment stages, we modelled the tree and shrub cover using the Random Forest algorithm.

Results

We found four types of B. litwinowii stands, characterized by different tree and shrub coverage (initial Bromus variegatus–Betula litwinowii encroachment indicating the first stage of succession, Aconitum nasutum–Betula litwinowii forest, Rubus idaeus–Betula litwinowii forest and Rhododendron caucasicum–Betula litwinowii tree line scrubs). B. litwinowii forest increased 25% compared to 1987 mainly in an uphill direction. Furthermore the modelled tree and shrub cover (R² = .69) could be related to the four vegetation types.

Conclusions

Our results indicate a recent trend towards shrub encroachment and consequently reforestation in the Kazbegi region.     

Maximum likelihood models and algorithms for gene tree evolution with duplications and losses

Background

The abundance of new genomic data provides the opportunity to map the location of gene duplication and loss events on a species phylogeny. The first methods for mapping gene duplications and losses were based on a parsimony criterion, finding the mapping that minimizes the number of duplication and loss events. Probabilistic modeling of gene duplication and loss is relatively new and has largely focused on birth-death processes.

Results

We introduce a new maximum likelihood model that estimates the speciation and gene duplication and loss events in a gene tree within a species tree with branch lengths. We also provide an, in practice, efficient algorithm that computes optimal evolutionary scenarios for this model. We implemented the algorithm in the program DrML and verified its performance with empirical and simulated data.

Conclusions

In test data sets, DrML finds optimal gene duplication and loss scenarios within minutes, even when the gene trees contain sequences from several hundred species. In many cases, these optimal scenarios differ from the lca-mapping that results from a parsimony gene tree reconciliation. Thus, DrML provides a new, practical statistical framework on which to study gene duplication.

     

Continental estimates of forest cover and forest cover changes in the dry ecosystems of Africa between 1990 and 2000

Aim

This study provides regional estimates of forest cover in dry African ecoregions and the changes in forest cover that occurred there between 1990 and 2000, using a systematic sample of medium‐resolution satellite imagery which was processed consistently across the continent.

Location

The study area corresponds to the dry forests and woodlands of Africa between the humid forests and the semi‐arid regions. This area covers the Sudanian and Zambezian ecoregions.

Methods

A systematic sample of 1600 Landsat satellite imagery subsets, each 20 km × 20 km in size, were analysed for two reference years: 1990 and 2000. At each sample site and for both years, dense tree cover, open tree cover, other wooded land and other vegetation cover were identified from the analysis of satellite imagery, which comprised multidate segmentation and automatic classification steps followed by visual control by national forestry experts.

Results

Land cover and land‐cover changes were estimated at continental and ecoregion scales and compared with existing pan‐continental, regional and local studies. The overall accuracy of our land‐cover maps was estimated at 87%. Between 1990 and 2000, 3.3 million hectares (Mha) of dense tree cover, 5.8 Mha of open tree cover and 8.9 Mha of other wooded land were lost, with a further 3.9 Mha degraded from dense to open tree cover. These results are substantially lower than the 34 Mha of forest loss reported in the FAO's 2010 Global Forest Resources Assessment for the same period and area.

Main conclusions

Our method generates the first consistent and robust estimates of forest cover and change in dry Africa with known statistical precision at continental and ecoregion scales. These results reduce the uncertainty regarding vegetation cover and its dynamics in these previously poorly studied ecosystems and provide crucial information for both science and environmental policies.     

Direct maximum parsimony phylogeny reconstruction from genotype data

Background  

Maximum parsimony phylogenetic tree reconstruction from genetic variation data is a fundamental problem in computational genetics with many practical applications in population genetics, whole genome analysis, and the search for genetic predictors of disease. Efficient methods are available for reconstruction of maximum parsimony trees from haplotype data, but such data are difficult to determine directly for autosomal DNA. Data more commonly is available in the form of genotypes, which consist of conflated combinations of pairs of haplotypes from homologous chromosomes. Currently, there are no general algorithms for the direct reconstruction of maximum parsimony phylogenies from genotype data. Hence phylogenetic applications for autosomal data must therefore rely on other methods for first computationally inferring haplotypes from genotypes.     

Five QTL hotspots for yield in short rotation coppice bioenergy poplar: The Poplar Biomass Loci

Background  

Concern over land use for non-food bioenergy crops requires breeding programmes that focus on producing biomass on the minimum amount of land that is economically-viable. To achieve this, the maximum potential yield per hectare is a key target for improvement. For long lived tree species, such as poplar, this requires an understanding of the traits that contribute to biomass production and their genetic control. An important aspect of this for long lived plants is an understanding of genetic interactions at different developmental stages, i.e. how genes or genetic regions impact on yield over time.     

A comparison of phylogenetic network methods using computer simulation

Background

We present a series of simulation studies that explore the relative performance of several phylogenetic network approaches (statistical parsimony, split decomposition, union of maximum parsimony trees, neighbor-net, simulated history recombination upper bound, median-joining, reduced median joining and minimum spanning network) compared to standard tree approaches, (neighbor-joining and maximum parsimony) in the presence and absence of recombination.

Principal Findings

In the absence of recombination, all methods recovered the correct topology and branch lengths nearly all of the time when the substitution rate was low, except for minimum spanning networks, which did considerably worse. At a higher substitution rate, maximum parsimony and union of maximum parsimony trees were the most accurate. With recombination, the ability to infer the correct topology was halved for all methods and no method could accurately estimate branch lengths.

Conclusions

Our results highlight the need for more accurate phylogenetic network methods and the importance of detecting and accounting for recombination in phylogenetic studies. Furthermore, we provide useful information for choosing a network algorithm and a framework in which to evaluate improvements to existing methods and novel algorithms developed in the future.     

Not only trees: Grasses determine African tropical biome distributions via water limitation and fire

Aim

Although much tropical ecology generally focuses on trees, grasses are fundamental for characterizing the extensive tropical grassy biomes (TGBs) and, together with the tree functional types, for determining the contrasting functional patterns of TGBs and tropical forests (TFs). To study the factors that determine African biome distribution and the transitions between them, we performed the first continental analysis to include grass and tree functional types.

Location

Sub‐Saharan Africa.

Time period

2000–2010.

Major taxa studied

Savanna and forest trees and C₄ grasses.

Methods

We combined remote‐sensing data with a land cover map, using tree functional types to identify TGBs and TFs. We analysed the relationships of grass and tree cover with fire interval, rainfall annual average and seasonality.

Results

In TGBs experiencing < 630 mm annual rainfall, grass growth was water limited. Grass cover and fire recurrence were strongly and directly related over the entire subcontinent. Some TGBs and TFs with annual rainfall > 1,200 mm had the same rainfall seasonality but displayed strongly different fire regimes.

Main conclusions

Water limitation to grass growth was fundamental in the driest TGBs, acting alongside the well‐known limitation to tree growth. Marked differences in fire regimes across all biomes indicated that fire was especially relevant for maintaining mesic and humid TGBs. At high rainfall, our results support the hypothesis of TGBs and TFs being alternative stable states maintained by a vegetation–fire feedback for similar climatic conditions.     

A life cycle greenhouse gas inventory of a tree production system

Purpose  

This study provides a detailed, process-based life cycle greenhouse gas (GHG) inventory of an ornamental tree production system for urban forestry. The success of large-scale tree planting initiatives for climate protection depends on projects being net sinks for CO₂ over their entire life cycle. However, previous assessments of urban tree planting initiatives have not accounted for the inputs required for tree production in nurseries, which include greenhouse systems, irrigation, and fertilization. A GHG inventory of nursery operations for tree production is a necessary step to assess the life cycle benefits or drawbacks of large-scale tree planting activities.     

Three-Dimensional Phylogeny Explorer: Distinguishing paralogs,lateral transfer,and violation of "molecular clock" assumption with 3D visualization

Background  

Construction and interpretation of phylogenetic trees has been a major research topic for understanding the evolution of genes. Increases in sequence data and complexity are creating a need for more powerful and insightful tree visualization tools.     

Inferring angiosperm phylogeny from EST data with widespread gene duplication

Background

Most studies inferring species phylogenies use sequences from single copy genes or sets of orthologs culled from gene families. For taxa such as plants, with very high levels of gene duplication in their nuclear genomes, this has limited the exploitation of nuclear sequences for phylogenetic studies, such as those available in large EST libraries. One rarely used method of inference, gene tree parsimony, can infer species trees from gene families undergoing duplication and loss, but its performance has not been evaluated at a phylogenomic scale for EST data in plants.

Results

A gene tree parsimony analysis based on EST data was undertaken for six angiosperm model species and Pinus, an outgroup. Although a large fraction of the tentative consensus sequences obtained from the TIGR database of ESTs was assembled into homologous clusters too small to be phylogenetically informative, some 557 clusters contained promising levels of information. Based on maximum likelihood estimates of the gene trees obtained from these clusters, gene tree parsimony correctly inferred the accepted species tree with strong statistical support. A slight variant of this species tree was obtained when maximum parsimony was used to infer the individual gene trees instead.

Conclusion

Despite the complexity of the EST data and the relatively small fraction eventually used in inferring a species tree, the gene tree parsimony method performed well in the face of very high apparent rates of duplication.

     

Rooted triple consensus and anomalous gene trees

Background  

Anomalous gene trees (AGTs) are gene trees with a topology different from a species tree that are more probable to observe than congruent gene trees. In this paper we propose a rooted triple approach to finding the correct species tree in the presence of AGTs.     

Performance of random forest when SNPs are in linkage disequilibrium

Background  

Single nucleotide polymorphisms (SNPs) may be correlated due to linkage disequilibrium (LD). Association studies look for both direct and indirect associations with disease loci. In a Random Forest (RF) analysis, correlation between a true risk SNP and SNPs in LD may lead to diminished variable importance for the true risk SNP. One approach to address this problem is to select SNPs in linkage equilibrium (LE) for analysis. Here, we explore alternative methods for dealing with SNPs in LD: change the tree-building algorithm by building each tree in an RF only with SNPs in LE, modify the importance measure (IM), and use haplotypes instead of SNPs to build a RF.     

Rooting a phylogenetic tree with nonreversible substitution models

Background  

We compared two methods of rooting a phylogenetic tree: the stationary and the nonstationary substitution processes. These methods do not require an outgroup.     

Towards sub-quadratic time and space complexity solutions for the dated tree reconciliation problem

Background

Recent coevolutionary analysis has considered tree topology as a means to reduce the asymptotic complexity associated with inferring the complex coevolutionary interrelationships that arise between phylogenetic trees. Targeted algorithmic design for specific tree topologies has to date been highly successful, with one recent formulation providing a logarithmic space complexity reduction for the dated tree reconciliation problem.

Methods

In this work we build on this prior analysis providing a further asymptotic space reduction, by providing a new formulation for the dynamic programming table used by a number of popular coevolutionary analysis techniques. This model gives rise to a sub quadratic running time solution for the dated tree reconciliation problem for selected tree topologies, and is shown to be, in practice, the fastest method for solving the dated tree reconciliation problem for expected evolutionary trees. This result is achieved through the analysis of not only the topology of the trees considered for coevolutionary analysis, but also the underlying structure of the dynamic programming algorithms that are traditionally applied to such analysis.

Conclusion

The newly inferred theoretical complexity bounds introduced herein are then validated using a combination of synthetic and biological data sets, where the proposed model is shown to provide an \(O(\sqrt{n})\) space saving, while it is observed to run in half the time compared to the fastest known algorithm for solving the dated tree reconciliation problem. What is even more significant is that the algorithm derived herein is able to guarantee the optimality of its inferred solution, something that algorithms of comparable speed have to date been unable to achieve.