Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree—a tree having its leaves labeled bijectively by elements of X and without degree-2 nodes—called the “species tree.” One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the “concordance” with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping—but not identical—sets of labels, is called “supertree.” In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of “containing as a minor” and “containing as a topological minor” in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees k, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time \(2^{O(k^2)} \cdot n\), where n is the total size of the input.     

Tree-Based Unrooted Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that are used to represent non-tree-like evolutionary histories that arise in organisms such as plants and bacteria, or uncertainty in evolutionary histories. An unrooted phylogenetic network on a non-empty, finite set X of taxa, or network, is a connected, simple graph in which every vertex has degree 1 or 3 and whose leaf set is X. It is called a phylogenetic tree if the underlying graph is a tree. In this paper we consider properties of tree-based networks, that is, networks that can be constructed by adding edges into a phylogenetic tree. We show that although they have some properties in common with their rooted analogues which have recently drawn much attention in the literature, they have some striking differences in terms of both their structural and computational properties. We expect that our results could eventually have applications to, for example, detecting horizontal gene transfer or hybridization which are important factors in the evolution of many organisms.     

Quarnet Inference Rules for Level-1 Networks

An important problem in phylogenetics is the construction of phylogenetic trees. One way to approach this problem, known as the supertree method, involves inferring a phylogenetic tree with leaves consisting of a set X of species from a collection of trees, each having leaf-set some subset of X. In the 1980s, Colonius and Schulze gave certain inference rules for deciding when a collection of 4-leaved trees, one for each 4-element subset of X, can be simultaneously displayed by a single supertree with leaf-set X. Recently, it has become of interest to extend this and related results to phylogenetic networks. These are a generalization of phylogenetic trees which can be used to represent reticulate evolution (where species can come together to form a new species). It has recently been shown that a certain type of phylogenetic network, called a (unrooted) level-1 network, can essentially be constructed from 4-leaved trees. However, the problem of providing appropriate inference rules for such networks remains unresolved. Here, we show that by considering 4-leaved networks, called quarnets, as opposed to 4-leaved trees, it is possible to provide such rules. In particular, we show that these rules can be used to characterize when a collection of quarnets, one for each 4-element subset of X, can all be simultaneously displayed by a level-1 network with leaf-set X. The rules are an intriguing mixture of tree inference rules, and an inference rule for building up a cyclic ordering of X from orderings on subsets of X of size 4. This opens up several new directions of research for inferring phylogenetic networks from smaller ones, which could yield new algorithms for solving the supernetwork problem in phylogenetics.     

Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.     

Phylogenetic relationships among cultivated <Emphasis Type="Italic">Zanthoxylum</Emphasis> species in China based on cpDNA markers

We here present a molecular phylogenetic analysis of cultivated Zanthoxylum species which have a long history of cultivation both for economic and for chemical values in China. Three cpDNA markers, including matK, rbcL, and trnL-F, were sequenced, with the goals of untangling phylogenetic relationships and inferring biogeographic origin and patterns of distribution among Zanthoxylum species. Based on three cpDNA markers, 19 haplotypes with 64 polymorphic sites in Zanthoxylum provenances were identified in our study. A low genetic differentiation (G _ST ?=?0.271, N _ST ?=?0.373) was observed within Zanthoxylum provenances. Based on phylogenetic tree and haplotype network, all 19 haplotypes were grouped into six clusters. Our results also supported the hypothesis that the so-called “Green Huajiao” belongs to the species Zanthoxylum armatum rather than Zanthoxylum schinifolium. The results also revealed that haplotypes of two cultivated species, Zanthoxylum bungeanum and Z. armatum, most probably diverged during the Late Miocene. Ancestral area reconstruction indicated that cultivated Zanthoxylum species experienced multiple long-distance dispersal events and several vicariance events and the ancestors of Zanthoxylum first colonized Yunnan and Guizhou provinces (D). Accordingly, the current disjunct distribution of Z. bungeanum and Z. armatum may represent long-distance dispersal of ancestors popularly named “Dahongpao” and “Qinghuajiao,” respectively. It is concluded that cpDNA markers may provide a new conceptual and practical opportunity to evaluate genetic diversity and to identify local cultivars of Zanthoxylum, making it a valuable source to include into potential breeding programs.     

Trinets encode tree-child and level-2 phylogenetic networks

Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that $\text{ level-1 }$ phylogenetic networks are encoded by their trinets, and also conjectured that all “recoverable” rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level-2 networks and binary tree-child networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets.     

Phylogenetic relationships of Aurantioideae (Rutaceae) based on RAD-Seq

The economically and nutritionally important genus Citrus belongs to the subfamily Aurantioideae in the family Rutaceae. Here, we analyzed the phylogenetic relationships of the subfamily Aurantioideae based on RAD-Seq. The RAD-Seq data produced phylogenetic trees with high support values, clear discriminations based on branch length, and elucidations of early branching events. Our genetic classification corresponded well with the classical morphological classification system and supported the subdivision of Citreae, one of two tribes of the Aurantioideae, into three subtribes—Triphasiinae, Citrinae, and Balsamocitrinae. Additionally, it was largely consistent with the subdivision of Clauseneae, the other tribe of the Aurantioideae, into three subtribes—Micromelinae, Clauseninae, and Merrillinae; the exception was Murraya paniculata. With the exception of members of primitive citrus fruit trees, namely, Severinia buxifolia and Hesperethusa crenulata, lower-level morphological groupings under subtribes based on genetic and morphological classifications corresponded well. The phylogenetic relationship between Asian “true citrus fruit trees” (genera Citrus, Poncirus, and Fortunella) and Australian/New Guinean citrus fruit trees (genera Microcitrus, Eremocitrus, and Clymenia) was inconsistent between present classification based mainly on the nuclear genome and the previous classification based on the chloroplast genome. This inconsistency may be explained by chloroplast capture. Our findings provide a valuable insight into the genetic relationships of the subfamily Aurantioideae in the family Rutaceae.     

Evolution and systematics of Green Bush-crickets (Orthoptera: Tettigoniidae: <Emphasis Type="Italic">Tettigonia</Emphasis>) in the Western Palaearctic: testing concordance between molecular,acoustic, and morphological data

The genus Tettigonia includes 26 species distributed in the Palaearctic region. Though the Green Bush-crickets are widespread in Europe and common in a variety of habitats throughout the Palaearctic ecozone, the genus is still in need of scientific attention due to the presence of a multitude of poorly explored taxa. In the present study, we sought to clarify the evolutionary relationships of Green Bush-crickets and the composition of taxa occurring in the Western Palaearctic. Based on populations from 24 disjunct localities, the phylogeny of the group was estimated using sequences of the cytochrome oxidase subunit I (COI) and the internal transcribed spacers 1 and 2 (ITS1 and ITS2). Morphological and acoustic variation documented for the examined populations and taxa was interpreted in the context of phylogenetic relationships inferred from our genetic analyses. The trees generated in the present study supported the existence of three main lineages: “A”—composed of all sampled populations of Tettigonia viridissima and the Tettigonia vaucheriana complex, “B”—comprising Tettigonia caudata, Tettigonia uvarovi, and the Tettigonia armeniaca complex, and “C”—consisting of Tettigonia cantans. The present study provides the first phylogenetic foundation for reviewing the systematics of Tettigonia (currently classified mostly according to morphological characteristics), proposing seven new synonymies.     

Relationships within <Emphasis Type="Italic">Capitotricha bicolor</Emphasis> (Lachnaceae,Ascomycota) as inferred from ITS rDNA sequences,including some notes on the <Emphasis Type="Italic">Brunnipila</Emphasis> and <Emphasis Type="Italic">Erioscyphella</Emphasis> clades

DNA sequences of Capitotricha bicolor from Quercus, Fagus sylvatica, Alnus alnobetula, and Nothofagus, and C. rubi from Rubus idaeus were obtained from apothecia to establish whether specimens from different hosts belong to separate species. The obtained ITS1–5.8S–ITS2 rDNA sequences were examined with Bayesian and parsimony phylogenetic analyses. Intra- and interspecific variation was also investigated based on molecular distances in the ITS region. The phylogenetic analyses supported the specific distinctness of Capitotricha rubi and the Capitotricha from Nothofagus, but also suggest specific distinctness between samples from Quercus, Fagus, and Alnus. The interspecific distances were larger than intraspecific distances for all examined units. The smallest distance was found between the “Alnus alnobetula” and “Fagus sylvatica” units. Two new sequences of Brunnipila are published. Capitotricha, Lachnum, and Erioscyphella are compared to each other based on hair and excipulum characteristics.     

Reconstructing Unrooted Phylogenetic Trees from Symbolic Ternary Metrics

Böcker and Dress (Adv Math 138:105–125, 1998) presented a 1-to-1 correspondence between symbolically dated rooted trees and symbolic ultrametrics. We consider the corresponding problem for unrooted trees. More precisely, given a tree T with leaf set X and a proper vertex coloring of its interior vertices, we can map every triple of three different leaves to the color of its median vertex. We characterize all ternary maps that can be obtained in this way in terms of 4- and 5-point conditions, and we show that the corresponding tree and its coloring can be reconstructed from a ternary map that satisfies those conditions. Further, we give an additional condition that characterizes whether the tree is binary, and we describe an algorithm that reconstructs general trees in a bottom-up fashion.     

NET: a new framework for the vectorization and examination of network data

Background

The analysis of complex networks both in general and in particular as pertaining to real biological systems has been the focus of intense scientific attention in the past and present. In this paper we introduce two tools that provide fast and efficient means for the processing and quantification of biological networks like Drosophila tracheoles or leaf venation patterns: the Network Extraction Tool (NET) to extract data and the Graph-edit-GUI (GeGUI) to visualize and modify networks.

Results

NET is especially designed for high-throughput semi-automated analysis of biological datasets containing digital images of networks. The framework starts with the segmentation of the image and then proceeds to vectorization using methodologies from optical character recognition. After a series of steps to clean and improve the quality of the extracted data the framework produces a graph in which the network is represented only by its nodes and neighborhood-relations. The final output contains information about the adjacency matrix of the graph, the width of the edges and the positions of the nodes in space. NET also provides tools for statistical analysis of the network properties, such as the number of nodes or total network length. Other, more complex metrics can be calculated by importing the vectorized network to specialized network analysis packages. GeGUI is designed to facilitate manual correction of non-planar networks as these may contain artifacts or spurious junctions due to branches crossing each other. It is tailored for but not limited to the processing of networks from microscopy images of Drosophila tracheoles.

Conclusion

The networks extracted by NET closely approximate the network depicted in the original image. NET is fast, yields reproducible results and is able to capture the full geometry of the network, including curved branches. Additionally GeGUI allows easy handling and visualization of the networks.

     

High-throughput sequencing of <Emphasis Type="Italic">Prunus ferganensis</Emphasis> indicates that it is a geographical population of <Emphasis Type="Italic">P. persica</Emphasis>

Peach belongs to the genus Prunus, which includes Prunus persica and its relative species, P. mira, P. davidiana, P. kansuensis, and P. ferganensis. Of these, P. ferganensis have been classified as a species, subspecies, or geographical population of P. persica. To explore the genetic difference between P. ferganensis and P. persica, high-throughput sequencing was used in different peach accessions belonging to different species. First, low-depth sequencing data of peach accessions belonging to four categories revealed that similarity between P. ferganensis and P. persica was similar to that between P. persica accessions from different geographical populations. Then, to further detect the genomic variation in P. ferganensis, the P. ferganensis accession “Xinjiang Pan Tao 1” and the P. persica accession “Xia Miao 1” were sequenced with high depth, and sequence reads were assembled. The results showed that the collinearity of “Xinjiang Pan Tao 1” with the reference genome “Lovell” was higher than that of “Xia Miao 1” and “Lovell” peach. Additionally, the number of genetic variants, including single nucleotide polymorphisms (SNPs), structural variations (SVs), and the specific genes annotated from unmapped sequence in “Xia Miao 1” was higher than that in “Xinjiang Pan Tao 1” peach. The data showed that there was a close distance between “Xinjiang Pan Tao 1” (P. ferganensis) and reference genome which belong to P. persica, comparing “Xia Miao 1” (P. persica) and reference ones. The results accompany with phylogenetic tree and structure analysis confirmed that P. ferganensis should be considered as a geographic population of P. persica rather than a subspecies or a distinct species. Furthermore, gene ontology analysis was performed using the gene comprising large-effect variation to understand the phenotypic difference between two accessions. The result revealed that the pathways of gene function affected by SVs but SNPs and insertion-deletions markedly differed between the two peach accessions.     

Methane formation and oxidation by prokaryotes

The review deals with systematization and generalization of new information concerning the phylogenetic and functional diversity of prokaryotes involved in the methane cycle. Methane is mostly produced by methanogenic archaea, which are responsible for the terminal stage of organic matter decomposition in a number of anoxic ecotopes. Although phylogeny, physiology, and biochemistry of methanogens have been extensively studied, important discoveries were made recently. Thus, members of deep phylogenetic lineages within the Euryarchaeota phylum (Methanomassiliicoccales, “Candidatus Methanofastidiosa,” “Methanonatronarchaeia”) and even outside it (“Ca. Verstraetearchaeota” and “Ca. Bathyarchaeota”) were reported to carry out methyl-reducing methanogenesis. Moreover, evidence was obtained on aerobic methane production by marine heterotrophic bacteria, which demethylate polysaccharide esters of methylphosphonic acid. Methanotrophic microorganisms oxidize methane both aerobically and anaerobically, decreasing significantly the release of this greenhouse gas into the atmosphere. In the presence of oxygen methane is oxidized by methanotrophic members of Alpha- and Gammaproteobacteria, as well as by Verrucomicrobia. Methanotrophic gammaproteobacteria have been recently revealed in hypoxic and even anoxic environments, where they probably oxidize methane either in a trophic consortium with oxygenic phototrophs and/or methylotrophs or using electron acceptors other than oxygen. Anaerobic methane oxidation has been known for a long time. Sulfat- and nitrate-dependent anaerobic methane oxidation carried out by the ANME archaea via reverse methanogenesis are the best studied processes. While metal-dependent anaerobic methane oxidation is considered possible, the mechanisms and agents responsible for this process have not been reliably identified. Intracellular oxygen production during nitrite-dependent anaerobic methane oxidation was shown for bacteria “Ca. Methylomirabilis oxyfera.” These findings stimulate interest in the processes and microorganisms of the methane cycle.     

Biologically feasible gene trees,reconciliation maps and informative triples

Background

The history of gene families—which are equivalent to event-labeled gene trees—can be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are biologically feasible, that is, if there is a possible true history that would explain a given gene tree. In practice, this problem is boiled down to finding a reconciliation map—also known as DTL-scenario—between the event-labeled gene trees and a (possibly unknown) species tree.

Results

In this contribution, we first characterize whether there is a valid reconciliation map for binary event-labeled gene trees T that contain speciation, duplication and horizontal gene transfer events and some unknown species tree S in terms of “informative” triples that are displayed in T and provide information of the topology of S. These informative triples are used to infer the unknown species tree S for T. We obtain a similar result for non-binary gene trees. To this end, however, the reconciliation map needs to be further restricted. We provide a polynomial-time algorithm to decide whether there is a species tree for a given event-labeled gene tree, and in the positive case, to construct the species tree and the respective (restricted) reconciliation map. However, informative triples as well as DTL-scenarios have their limitations when they are used to explain the biological feasibility of gene trees. While reconciliation maps imply biological feasibility, we show that the converse is not true in general. Moreover, we show that informative triples neither provide enough information to characterize “relaxed” DTL-scenarios nor non-restricted reconciliation maps for non-binary biologically feasible gene trees.

     

Hypercalcified segmented sponges (“sphinctozoans”) from the Upper Triassic (Norian) reef boulders of Taurus Mountains (southern Turkey)

Upper Triassic Norian reef boulders, exposed in a locality near the fountain “Tavuk Cesme” (“Chicken Fountain”) in Taurus Mountains, southern Turkey yielded a large number of hypercalcified sponges, including “sphinctozoans”, “inozoans”, “spongiomorphids”, and “chaetetids”. The sphinctozoans from this locality are described in this paper. Geologically, this locality belongs to the Anamas-Akseki autochthonous. The reef boulders of this locality are exposed near the “Tavuk Cesme” fountain, located at the road, leading from the town of Aksu to Yenisarbademli. The following taxa are described: Amblysiphonella taurica nov. sp., Anthalythalamia riedeli Senowbari-Daryan, Calabrisiphonella sphaerica nov. sp., Calabrisiphonella cuifi nov. sp., Cinnabaria minima Senowbari-Daryan, Colospongia recta nov. sp., Colospongia sp. 1, Colospongia sp. 2, Colospongia sp. 3, Cryptocoelia compacta nov. sp., Cryptocoelia? sp., Deningeria crassireticulata Senowbari-Daryan, Zühlke, Bechstädt and Flügel, Discosiphonella minima Senowbari-Daryan and Link, Gigantothalamia ovoidalis Senowbari-Daryan, Hajarispongia dipoyrazensis nov. sp., Hajarispongia cortexifera nov. sp., Kashanella irregularis Senowbari-Daryan, Kashanella cylindrica nov. sp., Parauvanella ferdowsensis Senowbari-Daryan, Parastylothalamia cylindrica nov. gen., nov. sp., Asiphothalamia polyosculata nov. gen, nov. sp., Sollasia norica nov. sp., and Thaumastocoelia sphaeroida Senowbari-Daryan. The most abundant sponge is Amblysiphonella taurica nov. sp. followed by Hajarispongia dipoyrazensis nov. sp., Colospongia and Discosiphonella minima Senowbari-Daryan and Link are also relatively abundant. The stylothalamid sponge Parastylothalamia nov. gen. is an abundant sponge genus in other Norian reefs of the Taurus Mountains, but is rare at the “Tavuk Cesme” locality.     

Application of quantitative measures of gene order similarity to phylogenetic reconstructions (exemplified by bacteria of the genus <Emphasis Type="Italic">Rickettsia</Emphasis>)

Data reflecting evolutionary changes in chromosomal gene order can be used for phylogenetic reconstructions along with the results of nucleotide sequence comparison. By the example of bacteria of the genus Rickettsia, we have shown that phylogenetic reconstructions based on quantitative estimates of the similarity and cladistic analysis of gene order data, may, in some cases, amend and fill up classical phylogenetic trees. When applied, these approaches enabled us to substantiate the hypothesis that Rickettsia felis species had split before the typhus (R. typhi, R. prowazekii) and spotted fever (R. connorii) group divergence and thus R. felis does not belong to the latter group. In general, rickettsias evolved towards increasing intracellular parasitic specialization. Five Rickettsia species whose genomes have been sequenced and annotated completely actually form an evolutionary series R. bellii—R. felis—R. conorii—R. prowazekii—R. typhi. Within this series, a reduction in genome size and rapid decrease of genome rearrangement rates (genome plasticity loss) gradually occur.     

Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems

Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time ${(1-\frac{1}{e})}$ -approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time ${(1-\frac{1}{e})}$ -approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et?al.     

Ecophysiology and polymorphism of the unicellular extremely natronophilic cyanobacterium <Emphasis Type="Italic">Euhalothece</Emphasis> sp. Z-M001 from Lake Magadi

Strain Z-M001 of a unicellular cyanobacterium, assigned by analysis of the 16S rRNA gene sequence to the phylogenetic group of the generic level Euhalothece, was isolated from soda Lake Magadi. It was shown that strain Z-M001, unlike all other known cultured and uncultured organisms of the Euhalothece group, is extremely natronophilic, and it was named accordingly “Euhalothece natronophila”. In its ecophysiological characteristics, it is comparable to extremely alkaliphilic organotrophic natronobacteria, which is essential for soda ecosystems, because cyanobacteria belong to primary producers. E. natronophila exhibits considerable morphological variability depending on the concentration of carbonates in the medium. The polymorphism of “ E. natronophila” is primarily connected to limitation by utilizable forms of carbon.