Computing the distribution of the Robinson-Foulds distance

With the exponential growth of genome databases, the importance of phylogenetics has increased dramatically over the past years. Studying phylogenetic trees enables us not only to understand how genes, genomes, and species evolve, but also helps us predict how they might change in future. One of the crucial aspects of phylogenetics is the comparison of two or more phylogenetic trees. There are different metrics for computing the dissimilarity between a pair of trees. The Robinson-Foulds (RF) distance is one of the widely used metrics on the space of labeled trees. The distribution of the RF distance from a given tree has been studied before, but the fastest known algorithm for computing this distribution is a slow, albeit polynomial-time, O(l⁵) algorithm. In this paper, we modify the dynamic programming algorithm for computing the distribution of this distance for a given tree by leveraging the number-theoretic transform (NTT), and improve the running time from O(l⁵) to O(l³ log l), where l is the number of tips of the tree. In addition to its practical usefulness, our method represents a theoretical novelty, as it is, to our knowledge, one of the rare applications of the number-theoretic transform for solving a computational biology problem.     

Rapid species identification of seafood spoilage and pathogenic Gram-positive bacteria by MALDI-TOF mass fingerprinting

The rapid identification of food pathogenic and spoilage bacteria is important to ensure food quality and safety. Seafood contaminated with pathogenic bacteria is one of the major causes of food intoxications, and the rapid spoilage of seafood products results in high economic losses. In this study, a collection of the main seafood pathogenic and spoilage Gram-positive bacteria was compiled, including Bacillus spp., Listeria spp., Clostridium spp., Staphylococcus spp. and Carnobacterium spp. The strains, belonging to 20 different species, were obtained from the culture collections and studied by matrix-assisted laser desorption ionization time-of-flight mass spectrometry (MALDI-TOF MS). A reference library was created, including the spectral fingerprints of 32 reference strains and the extracted peak lists with 10-30 peak masses. Genus-specific as well as species-specific peak masses were assigned and could serve as biomarkers for the rapid bacterial identification. Furthermore, the peak mass lists were clustered with the web-application SPECLUST to show the phyloproteomic relationships among the studied strains. Afterwards, the method was successfully applied to identify six strains isolated from seafood by comparison with the reference library. Additionally, phylogenetic analysis based on the 16S rRNA gene was carried out and contrasted with the proteomic approach. This is the first time MALDI-TOF MS fingerprinting is applied to Gram-positive bacterial identification in seafood, being a fast and accurate technique to ensure seafood quality and safety.     

An information theory perspective on the balanced minimum evolution problem

We show that the Balanced Minimum Evolution Problem (BMEP) is a cross-entropy minimization problem. This new perspective both extends the previous interpretations of the BMEP length function described in the literature and enables the identification of an efficiently computable family of lower bounds on the value of the optimal solution to the problem.     

FluClass: A novel algorithm and approach to score and visualize the phylogeny of the influenza virus using mass spectrometry

A novel computer algorithm FluClass has been developed to facilitate the phylogenetic classification of influenza virus using mass spectral data. FluClass accepts a DNA or protein-based phylogenetic tree as input and generates theoretical peptide mass lists for each node. An experimental mass spectrum from an influenza virus protein digest is then placed onto the phylogenetic tree using a novel random resampling function (Z-score) that allows the scoring of spectrum against both internal and leaf nodes. Testing of the algorithm using hemagglutinin protein sequences from human-host influenza viruses showed that the Z-score performs comparably to the Profound scoring method for the scoring of leaf nodes and is substantially better at scoring internal nodes. Scoring of internal nodes allows colorizations of nodes of the phylogenetic tree enabling the classification of the query spectrum to be rapidly visualized. Finally we demonstrate the utility of FluClass on experimental spectra from six strains. Given that mass spectrometry data can be generated rapidly for influenza virus proteins, FluClass provides a fast and direct method for phylogenetic analysis of influenza proteins.     

Live phylogeny with polytomies: Finding the most compact parsimonious trees

Construction of phylogenetic trees has traditionally focused on binary trees where all species appear on leaves, a problem for which numerous efficient solutions have been developed. Certain application domains though, such as viral evolution and transmission, paleontology, linguistics, and phylogenetic stemmatics, often require phylogeny inference that involves placing input species on ancestral tree nodes (live phylogeny), and polytomies. These requirements, despite their prevalence, lead to computationally harder algorithmic solutions and have been sparsely examined in the literature to date. In this article we prove some unique properties of most parsimonious live phylogenetic trees with polytomies, and their mapping to traditional binary phylogenetic trees. We show that our problem reduces to finding the most compact parsimonious tree for n species, and describe a novel efficient algorithm to find such trees without resorting to exhaustive enumeration of all possible tree topologies.     

Evaluating linguistic distance measures

In Ref. [13], Petroni and Serva discuss the use of Levenshtein distances (LD) between words referring to the same concepts as a tool for establishing overall distances among languages which can then subsequently be used to derive phylogenies. The authors modify the raw LD by dividing the LD by the length of the longer of the two words compared, to produce what could be called LDN (normalized LD). Other scholars [7] and [8] have used a further modification, where they divide the LDN by the average LDN among words not referring to the same concept. This produces what could be called LDND. The authors of Ref. [13] question whether LDND is a more adequate measure of distance than LDN. Here we show empirically that LDND is the better measure in the situation where the languages compared have not already been shown, by other, more traditional methods of comparative linguistics, to be related. If automated language classification is to be used as a tool independent of traditional methods then the further modification is necessary.     

A correct proof of the McMorris-Powers’ theorem on the consensus of phylogenies

McMorris and Powers proved an Arrow-type theorem on phylogenies given as collections of quartets. There is an error in one of the main lemmas used to prove this theorem. However, this lemma (and thereby the theorem) is still true, and we provide a corrected proof.