Consistency of the neighbor-net algorithm

NeighborNet: improved algorithms and implementation

NeighborNet constructs phylogenetic networks to visualize distance data. It is a popular method used in a wide range of applications. While several studies have investigated its mathematical features, here we focus on computational aspects. The algorithm operates in three steps. We present a new simplified formulation of the first step, which aims at computing a circular ordering. We provide the first technical description of the second step, the estimation of split weights. We review the third step by constructing and drawing the network. Finally, we discuss how the networks might best be interpreted, review related approaches, and present some open questions.

Phylogenetic Networks as Circuits With Resistance Distance

Phylogenetic networks are notoriously difficult to reconstruct. Here we suggest that it can be useful to view unknown genetic distance along edges in phylogenetic networks as analogous to unknown resistance in electric circuits. This resistance distance, well-known in graph theory, turns out to have nice mathematical properties which allow the precise reconstruction of networks. Specifically we show that the resistance distance for a weighted 1-nested network is Kalmanson, and that the unique associated circular split network fully represents the splits of the original phylogenetic network (or circuit). In fact, this full representation corresponds to a face of the balanced minimal evolution polytope for level-1 networks. Thus, the unweighted class of the original network can be reconstructed by either the greedy algorithm neighbor-net or by linear programming over a balanced minimal evolution polytope. We begin study of 2-nested networks with both minimum path and resistance distance, and include some counting results for 2-nested networks.

Mycorrhiza: genotype assignment using phylogenetic networks

MOTIVATION

The genotype assignment problem consists of predicting, from the genotype of an individual, which of a known set of populations it originated from. The problem arises in a variety of contexts, including wildlife forensics, invasive species detection and biodiversity monitoring. Existing approaches perform well under ideal conditions but are sensitive to a variety of common violations of the assumptions they rely on.

RESULTS

In this article, we introduce Mycorrhiza, a machine learning approach for the genotype assignment problem. Our algorithm makes use of phylogenetic networks to engineer features that encode the evolutionary relationships among samples. Those features are then used as input to a Random Forests classifier. The classification accuracy was assessed on multiple published empirical SNP, microsatellite or consensus sequence datasets with wide ranges of size, geographical distribution and population structure and on simulated datasets. It compared favorably against widely used assessment tests or mixture analysis methods such as STRUCTURE and Admixture, and against another machine-learning based approach using principal component analysis for dimensionality reduction. Mycorrhiza yields particularly significant gains on datasets with a large average fixation index (FST) or deviation from the Hardy-Weinberg equilibrium. Moreover, the phylogenetic network approach estimates mixture proportions with good accuracy.

AVAILABILITY AND IMPLEMENTATION

Mycorrhiza is released as an easy to use open-source python package at github.com/jgeofil/mycorrhiza.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Genetic Diversity Among Mycobacterium avium Subspecies Revealed by Analysis of Complete Genome Sequences

Mycobacterium avium comprises four subspecies that contain both human and veterinary pathogens. At the inception of this study, twenty-eight M. avium genomes had been annotated as RefSeq genomes, facilitating direct comparisons. These genomes represent strains from around the world and provided a unique opportunity to examine genome dynamics in this species. Each genome was confirmed to be classified correctly based on SNP genotyping, nucleotide identity and presence/absence of repetitive elements or other typing methods. The Mycobacterium avium subspecies paratuberculosis (Map) genome size and organization was remarkably consistent, averaging 4.8 Mb with a variance of only 29.6 kb among the 13 strains. Comparing recombination events along with the larger genome size and variance observed among Mycobacterium avium subspecies avium (Maa) and Mycobacterium avium subspecies hominissuis (Mah) strains (collectively termed non-Map) suggests horizontal gene transfer occurs in non-Map, but not in Map strains. Overall, M. avium subspecies could be divided into two major sub-divisions, with the Map type II (bovine strains) clustering tightly on one end of a phylogenetic spectrum and Mah strains clustering more loosely together on the other end. The most evolutionarily distinct Map strain was an ovine strain, designated Telford, which had >1,000 SNPs and showed large rearrangements compared to the bovine type II strains. The Telford strain clustered with Maa strains as an intermediate between Map type II and Mah. SNP analysis and genome organization analyses repeatedly demonstrated the conserved nature of Map versus the mosaic nature of non-Map M. avium strains. Finally, core and pangenomes were developed for Map and non-Map strains. A total of 80% Map genes belonged to the Map core genome, while only 40% of non-Map genes belonged to the non-Map core genome. These genomes provide a more complete and detailed comparison of these subspecies strains as well as a blueprint for how genetic diversity originated.

Level-1 phylogenetic networks and their balanced minimum evolution polytopes

Balanced minimum evolution is a distance-based criterion for the reconstruction of phylogenetic trees. Several algorithms exist to find the optimal tree with respect to this criterion. One approach is to minimize a certain linear functional over an appropriate polytope. Here we present polytopes that allow a similar linear programming approach to finding phylogenetic networks. We investigate a two-parameter family of polytopes that arise from phylogenetic networks, and which specialize to the Balanced Minimum Evolution polytopes as well as the Symmetric Travelling Salesman polytopes. We show that the vertices correspond to certain level-1 phylogenetic networks, and that there are facets or faces for every split. We also describe lower bound faces and a family of faces for every dimension.

NANUQ: a method for inferring species networks from gene trees under the coalescent model

Species networks generalize the notion of species trees to allow for hybridization or other lateral gene transfer. Under the network multispecies coalescent model, individual gene trees arising from a network can have any topology, but arise with frequencies dependent on the network structure and numerical parameters. We propose a new algorithm for statistical inference of a level-1 species network under this model, from data consisting of gene tree topologies, and provide the theoretical justification for it. The algorithm is based on an analysis of quartets displayed on gene trees, combining several statistical hypothesis tests with combinatorial ideas such as a quartet-based intertaxon distance appropriate to networks, the NeighborNet algorithm for circular split systems, and the Circular Network algorithm for constructing a splits graph.

Symbols in motion: Flexible cultural boundaries and the fast spread of the Neolithic in the western Mediterranean

The rapid diffusion of farming technologies in the western Mediterranean raises questions about the mechanisms that drove the development of intensive contact networks and circulation routes between incoming Neolithic communities. Using a statistical method to analyze a brand-new set of cultural and chronological data, we document the large-scale processes that led to variations between Mediterranean archaeological cultures, and micro-scale processes responsible for the transmission of cultural practices within farming communities. The analysis of two symbolic productions, pottery decorations and personal ornaments, shed light on the complex interactions developed by Early Neolithic farmers in the western Mediterranean area. Pottery decoration diversity correlates with local processes of circulation and exchange, resulting in the emergence and the persistence of stylistic and symbolic boundaries between groups, while personal ornaments reflect extensive networks and the high level of mobility of Early Neolithic farmers. The two symbolic productions express different degrees of cultural interaction that may have facilitated the successful and rapid expansion of early farming societies in the western Mediterranean.

Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem

Clusters of paralogous genes such as the famous HOX cluster of developmental transcription factors tend to evolve by stepwise duplication of its members, often involving unequal crossing over. Gene conversion and possibly other mechanisms of concerted evolution further obfuscate the phylogenetic relationships. As a consequence, it is very difficult or even impossible to disentangle the detailed history of gene duplications in gene clusters. In this contribution we show that the expansion of gene clusters by unequal crossing over as proposed by Walter Gehring leads to distinctive patterns of genetic distances, namely a subclass of circular split systems. Furthermore, when the gene cluster was left undisturbed by genome rearrangements, the shortest Hamiltonian paths with respect to genetic distances coincide with the genomic order. This observation can be used to detect ancient genomic rearrangements of gene clusters and to distinguish gene clusters whose evolution was dominated by unequal crossing over within genes from those that expanded through other mechanisms.

The recombination dynamics of Staphylococcus aureus inferred from spA gene

Background

Given the role of spA as a pivotal virulence factor decisive for Staphylococcus aureus ability to escape from innate and adaptive immune responses, one can consider it as an object subject to adaptive evolution and that variations in spA may uncover pathogenicity variations.

Results

The population genetic structure was deduced from the extracellular domains of SpA gene sequence (domains A-E and the X-region) and compared to the MLST-analysis of 41 genetically diverse methicillin-resistant (MRSA) and methicillin-susceptible (MSSA) S. aureus strains. Incongruence between tree topologies was noticeable and in the inferred spA tree most MSSA isolates were clustered in a distinct group. Conversely, the distribution of strains according to their spA-type was not always congruent with the tree inferred from the complete spA gene foreseeing that spA is a mosaic gene composed of different segments exhibiting different evolutionary histories. Evidences of a network-like organization were identified through several conflicting phylogenetic signals and indeed several intragenic recombination events (within subdomains of the gene) were detected within and between CC’s of MRSA strains. The alignment of SpA sequences enabled the clustering of several isoforms as a result of non-randomly distributed amino acid variations, located in two clusters of polymorphic sites in domains D to B and Xr (a). Nevertheless, evidences of cluster specific structural arrangements were detected reflecting alterations on specific residues with potential impact on S. aureus pathogenicity.

Conclusions

The detection of positive selection operating on spA combined with frequent non-synonymous mutations, domain duplication and frequent intragenic recombination events represent important mechanisms acting in the evolutionary adaptive mechanism promoting spA genetic plasticity. These findings argue that crucial allelic forms correlated with pathogenicity can be identified by sequences analysis enabling the design of more robust schemes.

Electronic supplementary material

The online version of this article (doi:10.1186/s12866-016-0757-9) contains supplementary material, which is available to authorized users.

Progressive alignment of genomic signals by multiple dynamic time warping

This paper presents the utilization of progressive alignment principle for positional adjustment of a set of genomic signals with different lengths. The new method of multiple alignment of signals based on dynamic time warping is tested for the purpose of evaluating the similarity of different length genes in phylogenetic studies. Two sets of phylogenetic markers were used to demonstrate the effectiveness of the evaluation of intraspecies and interspecies genetic variability. The part of the proposed method is modification of pairwise alignment of two signals by dynamic time warping with using correlation in a sliding window. The correlation based dynamic time warping allows more accurate alignment dependent on local homologies in sequences without the need of scoring matrix or evolutionary models, because mutual similarities of residues are included in the numerical code of signals.

IDENTIFYING AND RECONSTRUCTING LATERAL TRANSFERS FROM DISTANCE MATRICES BY COMBINING THE MINIMUM CONTRADICTION METHOD AND NEIGHBOR-NET

Identifying lateral gene transfers is an important problem in evolutionary biology. Under a simple model of evolution, the expected values of an evolutionary distance matrix describing a phylogenetic tree fulfill the so-called Kalmanson inequalities. The Minimum Contradiction method for identifying lateral gene transfers exploits the fact that lateral transfers may generate large deviations from the Kalmanson inequalities. Here a new approach is presented to deal with such cases that combines the Neighbor-Net algorithm for computing phylogenetic networks with the Minimum Contradiction method. A subset of taxa, prescribed using Neighbor-Net, is obtained by measuring how closely the Kalmanson inequalities are fulfilled by each taxon. A criterion is then used to identify the taxa, possibly involved in a lateral transfer between nonconsecutive taxa. We illustrate the utility of the new approach by applying it to a distance matrix for Archaea, Bacteria, and Eukaryota.

Tanglegrams for rooted phylogenetic trees and networks

Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks.

Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets.

Availability: The algorithm is implemented in our program Dendroscope 3, which is freely available from www.dendroscope.org.

Contact:scornava@informatik.uni-tuebingen.de; huson@informatik.uni-tuebingen.de

Of woods and webs: possible alternatives to the tree of life for studying genomic fluidity in E. coli

Background

We introduce several forest-based and network-based methods for exploring microbial evolution, and apply them to the study of thousands of genes from 30 strains of E. coli. This case study illustrates how additional analyses could offer fast heuristic alternatives to standard tree of life (TOL) approaches.

Results

We use gene networks to identify genes with atypical modes of evolution, and genome networks to characterize the evolution of genetic partnerships between E. coli and mobile genetic elements. We develop a novel polychromatic quartet method to capture patterns of recombination within E. coli, to update the clanistic toolkit, and to search for the impact of lateral gene transfer and of pathogenicity on gene evolution in two large forests of trees bearing E. coli. We unravel high rates of lateral gene transfer involving E. coli (about 40% of the trees under study), and show that both core genes and shell genes of E. coli are affected by non-tree-like evolutionary processes. We show that pathogenic lifestyle impacted the structure of 30% of the gene trees, and that pathogenic strains are more likely to transfer genes with one another than with non-pathogenic strains. In addition, we propose five groups of genes as candidate mobile modules of pathogenicity. We also present strong evidence for recent lateral gene transfer between E. coli and mobile genetic elements.

Conclusions

Depending on which evolutionary questions biologists want to address (i.e. the identification of modules, genetic partnerships, recombination, lateral gene transfer, or genes with atypical evolutionary modes, etc.), forest-based and network-based methods are preferable to the reconstruction of a single tree, because they provide insights and produce hypotheses about the dynamics of genome evolution, rather than the relative branching order of species and lineages. Such a methodological pluralism - the use of woods and webs - is to be encouraged to analyse the evolutionary processes at play in microbial evolution.

This manuscript was reviewed by: Ford Doolittle, Tal Pupko, Richard Burian, James McInerney, Didier Raoult, and Yan Boucher

Improved phylogenetic analyses corroborate a plausible position of Martialis heureka in the ant tree of life

Martialinae are pale, eyeless and probably hypogaeic predatory ants. Morphological character sets suggest a close relationship to the ant subfamily Leptanillinae. Recent analyses based on molecular sequence data suggest that Martialinae are the sister group to all extant ants. However, by comparing molecular studies and different reconstruction methods, the position of Martialinae remains ambiguous. While this sister group relationship was well supported by Bayesian partitioned analyses, Maximum Likelihood approaches could not unequivocally resolve the position of Martialinae. By re-analysing a previous published molecular data set, we show that the Maximum Likelihood approach is highly appropriate to resolve deep ant relationships, especially between Leptanillinae, Martialinae and the remaining ant subfamilies. Based on improved alignments, alignment masking, and tree reconstructions with a sufficient number of bootstrap replicates, our results strongly reject a placement of Martialinae at the first split within the ant tree of life. Instead, we suggest that Leptanillinae are a sister group to all other extant ant subfamilies, whereas Martialinae branch off as a second lineage. This assumption is backed by approximately unbiased (AU) tests, additional Bayesian analyses and split networks. Our results demonstrate clear effects of improved alignment approaches, alignment masking and data partitioning. We hope that our study illustrates the importance of thorough, comprehensible phylogenetic analyses using the example of ant relationships.

Complete mitochondrial genome of a Pleistocene jawbone unveils the origin of polar bear

The polar bear has become the flagship species in the climate-change discussion. However, little is known about how past climate impacted its evolution and persistence, given an extremely poor fossil record. Although it is undisputed from analyses of mitochondrial (mt) DNA that polar bears constitute a lineage within the genetic diversity of brown bears, timing estimates of their divergence have differed considerably. Using next-generation sequencing technology, we have generated a complete, high-quality mt genome from a stratigraphically validated 130,000- to 110,000-year-old polar bear jawbone. In addition, six mt genomes were generated of extant polar bears from Alaska and brown bears from the Admiralty and Baranof islands of the Alexander Archipelago of southeastern Alaska and Kodiak Island. We show that the phylogenetic position of the ancient polar bear lies almost directly at the branching point between polar bears and brown bears, elucidating a unique morphologically and molecularly documented fossil link between living mammal species. Molecular dating and stable isotope analyses also show that by very early in their evolutionary history, polar bears were already inhabitants of the Artic sea ice and had adapted very rapidly to their current and unique ecology at the top of the Arctic marine food chain. As such, polar bears provide an excellent example of evolutionary opportunism within a widespread mammalian lineage.

Noisy: identification of problematic columns in multiple sequence alignments

MOTIVATION

Sequence-based methods for phylogenetic reconstruction from (nucleic acid) sequence data are notoriously plagued by two effects: homoplasies and alignment errors. Large evolutionary distances imply a large number of homoplastic sites. As most protein-coding genes show dramatic variations in substitution rates that are not uncorrelated across the sequence, this often leads to a patchwork pattern of (i) phylogenetically informative and (ii) effectively randomized regions. In highly variable regions, furthermore, alignment errors accumulate resulting in sometimes misleading signals in phylogenetic reconstruction.

RESULTS

We present here a method that, based on assessing the distribution of character states along a cyclic ordering of the taxa, allows the identification of phylogenetically uninformative homoplastic sites in a multiple sequence alignment. Removal of these sites appears to improve the performance of phylogenetic reconstruction algorithms as measured by various indices of "tree quality". In particular, we obtain more stable trees due to the exclusion of phylogenetically incompatible sites that most likely represent strongly randomized characters.

SOFTWARE

The computer program noisy implements this approach. It can be employed to improving phylogenetic reconstruction capability with quite a considerable success rate whenever (1) the average bootstrap support obtained from the original alignment is low, and (2) there are sufficiently many taxa in the data set - at least, say, 12 to 15 taxa. The software can be obtained under the GNU Public License from http://www.bioinf.uni-leipzig.de/Software/noisy/.

Progressive multiple sequence alignments from triplets

Background

The quality of progressive sequence alignments strongly depends on the accuracy of the individual pairwise alignment steps since gaps that are introduced at one step cannot be removed at later aggregation steps. Adjacent insertions and deletions necessarily appear in arbitrary order in pairwise alignments and hence form an unavoidable source of errors.

Research

Here we present a modified variant of progressive sequence alignments that addresses both issues. Instead of pairwise alignments we use exact dynamic programming to align sequence or profile triples. This avoids a large fractions of the ambiguities arising in pairwise alignments. In the subsequent aggregation steps we follow the logic of the Neighbor-Net algorithm, which constructs a phylogenetic network by step-wisely replacing triples by pairs instead of combining pairs to singletons. To this end the three-way alignments are subdivided into two partial alignments, at which stage all-gap columns are naturally removed. This alleviates the "once a gap, always a gap" problem of progressive alignment procedures.

Conclusion

The three-way Neighbor-Net based alignment program aln3nn is shown to compare favorably on both protein sequences and nucleic acids sequences to other progressive alignment tools. In the latter case one easily can include scoring terms that consider secondary structure features. Overall, the quality of resulting alignments in general exceeds that of clustalw or other multiple alignments tools even though our software does not included heuristics for context dependent (mis)match scores.