Molecular polytomies

This paper focuses on polytomies, especially molecular polytomies. The distinction between molecular and species polytomies is important, but is often not made. Likelihood ratio tests are an easier method for detecting molecular polytomies than other methods cited herein. Simulation shows that parsimony will generally falsely resolve molecular polytomies, which is worrisome because a simple mathematical model described herein predicts that molecular polytomies will occur often when the mean branch length is small. A test of the model using several real molecular data sets indicates that molecular polytomies may actually occur more often than predicted by the model. This suggests that at least some published molecular parsimony trees contain clades that are false resolutions of polytomies. Finally, a possible method for detecting species polytomies from molecular data is described.     

RECONSTRUCTING CHARACTER EVOLUTION ON POLYTOMOUS CLADOGRAMS

Abstract— Algorithms to reconstruct character evolution on polytomous cladograms or phylogenetic trees have to date interpreted each polytomy literally, as if it were an event of multiple speciation, with multiple daughter species descending independently from a mother species, thus requiring any similarities shared by only some of these daughters to be accounted for by convergence. These algorithms are not appropriate when the polytomy is interpreted in the usual way, namely as representing uncertainty in the cladogram's resolution. New algorithms for both ordered and unordered characters are presented to reconstruct character evolution under the uncertain-resolution interpretation of polytomies. These algorithms allow the cladogram to resolve itself so as to be favourable for the character whose evolution is being reconstructed. Because different characters may have different favourable resolutions, it is not possible in general to use these algorithms to determine the total parsimony of a polytomous cladogram (the number of evolutionary steps required over all characters by the cladogram), for which the only adequate approach is to find a most parsimonious dichotomous resolution of the cladogram.     

Fast Fitch-Parsimony Algorithms for Large Data Sets

The speed of analytical algorithms becomes increasingly important as systematists accumulate larger data sets. In this paper I discuss several time-saving modifications to published Fitch-parsimony tree search algorithms, including shortcuts that allow rapid evaluation of tree lengths and fast reoptimization of trees after clipping or joining of subtrees, as well as search strategies that allows one to successively increase the exhaustiveness of branch swapping. I also describe how Fitch-parsimony algorithms can be restructured to take full advantage of the computing power of modern microprocessors by horizontal or vertical packing of characters, allowing simultaneous processing of many characters, and by avoidance of conditional branches that disturb instruction flow. These new multicharacter algorithms are particularly useful for large data sets of characters with a small number of states, such as nucleotide characters. As an example, the multicharacter algorithms are estimated to be 3.6–10 times faster than single-character equivalents on a PowerPC 604. The speed gain is even larger on processors using MMX, Altivec or similar technologies allowing single instructions to be performed on multiple data simultaneously.     

Searching for Most Parsimonious Trees with Simulated Evolutionary Optimization

This study describes novel algorithms for searching for most parsimonious trees. These algorithms are implemented as a parsimony computer program, PARSIGAL, which performs well even with difficult data sets. For high level search, PARSIGAL uses an evolutionary optimization algorithm, which feeds good tree candidates to a branch-swapping local search procedure. This study also describes an extremely fast method of recomputing state sets for binary characters (additive or nonadditive characters with two states), based on packing 32 characters into a single memory word and recomputing the tree simultaneously for all 32 characters using fast bitwise logical operations. The operational principles of PARSIGAL are quite different from those previously published for other parsimony computer programs. Hence it is conceivable that PARSIGAL may be able to locate islands of trees that are different from those that are easily located with existing parsimony computer programs.     

METHODS FOR FASTER PARSIMONY ANALYSIS

Abstract — Several algorithms to speed up branch swapping searches for most parsimonious trees are described. The method for indirect tree length calculation when moving a clipped clade, based on final states for the divided tree, is expanded to take into account polymorphic characters, and to include the possibility of rejecting several locations as suboptimal by checking just one node. Three different algorithms for faster estimation of final state assignments for the divided tree based on calculations for the whole tree are presented. The first of these is approximate; it uses information from the final state sets for the whole tree. The second is exact, but it is slower than the first, and requires more memory; it is based on the union of the state sets of the descendants for each node. The third is also exact; it requires more memory and programming effort than the other two but it is faster, it is based on final and preliminary state sets for the whole tree ("incremental two-pass optimization"). Efficient ways to derive state assignments for collapsing trees, based on final states for the divided tree, are described. The recently proposed method of "incremental optimization" is discussed. It is likely that searches using that method will be no faster than searches using indirect calculation as originally described, and will be quite slower than the modified indirect calculation described here. Searches using that method will probably be significantly slowed down when zero-length branches are to be collapsed, since shortcuts for faster collapsing are not directly applicable.     

Untangling the contribution of characters to evolutionary relationships: a case study using fossils,morphology, and Genes

Given the importance of phylogenetic trees to understanding common ancestry and evolution, they are a necessary part of the undergraduate biology curriculum. However, a number of common misconceptions, such as reading across branch tips and understanding homoplasy, can pose difficulties in student understanding. Students also may take phylogenetic trees to be fact, instead of hypotheses. Below we outline a case study that we have used in upper-level undergraduate evolution and ichthyology courses that utilizes shark teeth (representing fossils), body characters, and mitochondrial genes. Students construct their own trees using freely available software, and are prompted to compare their trees with a series of questions. Finally, students explore homoplasy, polytomies, and trees as hypotheses during a class discussion period. This case study gives students practice with tree-thinking, as well as demonstrating that tree topology is reliant on which characters and tree-building algorithms are used.     

Model‐based approach to test hard polytomies in the Eulaemus clade of the most diverse South American lizard genus Liolaemus (Liolaemini,Squamata)

Lack of resolution in a phylogenetic tree is usually represented as a polytomy, and often adding more data (loci and taxa) resolves the species tree. These are the ‘soft’ polytomies, but in other cases additional data fail to resolve relationships; these are the ‘hard’ polytomies. This latter case is often interpreted as a simultaneous radiation of lineages in the history of a clade. Although hard polytomies are difficult to address, model‐based approaches provide new tools to test these hypotheses. Here, we used a clade of 144 species of the South American lizard clade Eulaemus to estimate phylogenies using a traditional concatenated matrix and three species tree methods: *BEAST, BEST, and minimizing deep coalescences (MDC). The different species tree methods recovered largely discordant results, but all resolved the same polytomy (e.g. very short internodes amongst lineages and low nodal support in Bayesian methods). We simulated data sets under eight explicit evolutionary models (including hard polytomies), tested these against empirical data (a total of 14 loci), and found support for two polytomies as the most plausible hypothesis for diversification of this clade. We discuss the performance of these methods and their limitations under the challenging scenario of hard polytomies. © 2015 The Linnean Society of London     

Confidence Intervals for Morphology-Based Cladistic Trees: A Platyrrhine Phylogeny Test Case

I estimate confidence intervals for phylogenetic trees based on bootstrap resampling while calculating special coefficients of similarity. I treat each successive cladistic dichotomy as a null hypothesis for sampling from a universe of cranial and postcranial synapomorphically-based similarities that includes the next lower similarity. Successive dichotomies that are not at significantly different similarity levels are collapsed into polytomies. Following a trial application to equid cladistic traits employed in Felsenstein's introduction (Felsenstein, J. (1985). Evolution 39: 783–791), I apply the methods to New World monkey relationships using morphological character sets. Unresolvable polytomies among platyrrhine subfamilies are the rule when these methods are applied.     

Are phylogenies resolved at the genus level appropriate for studies on phylogenetic structure of species assemblages?

Phylogenies are essential to studies investigating the effect of evolutionary history on assembly of species in ecological communities and geographical and ecological patterns of phylogenetic structure of species assemblages. Because phylogenies well resolved at the species level are lacking for many major groups of organisms such as vascular plants, researchers often generate a species-level phylogenies using a phylogeny well resolved at the genus level as a backbone and attaching species to their respective genera in the phylogeny as polytomies or by using a megaphylogeny well resolved at the genus level as a backbone and adding additional species to the megaphylogeny as polytomies of their respective genera. However, whether the result of a study using species-level phylogenies generated in these ways is robust, compared to that based on phylogenies fully resolved at the species level, has not been assessed. Here, we use 1093 angiosperm tree assemblages (each in a 110 × 110 km quadrat) in North America as a model system to address this question, by examining six commonly used metrics of phylogenetic structure (phylogenetic diversity and phylogenetic relatedness) and six climate variables commonly used in ecology. Our results showed that (1) the scores of phylogenetic metrics derived from species-level phylogenies resolved at the genus level with species being attached to their respective genera as polytomies are very strongly or perfectly correlated to those derived from a phylogeny fully resolved at the species level (the mean of correlation coefficients is 0.973), and (2) the relationships between the scores of phylogenetic metrics and climate variables are consistent between the two sets of analyses based on the two types of phylogeny. Our study suggests that using species-level phylogenies resolved at the genus level with species being attached to their genera as polytomies is appropriate in studies exploring patterns of phylogenetic structure of species in ecological communities across geographical and ecological gradients.     

An improved algorithm for finding diagnostic taxonomic descriptions

A computer program is described which finds sets of diagnostic characters for the recognition of species. Unlike previous algorithms, it finds all the possible sets requested and will also run with reasonable demands on computer time and storage. The program will search for sets with a specified size range and with a given minimum number of diagnostic characters to distinguish a taxon from all the others.     

Phylogenetic analysis of the genus <Emphasis Type="Italic">Argia</Emphasis> Rambur, 1842 (Odonata: Coenagrionidae), based on morphological characters of larvae and mitochondrial DNA sequences

The study of the evolutionary interrelationships among the species encompassed in the Neotropical genus Argia (Zygoptera: Coenagrionidae) has been neglected. The goal of this study is to infer the phylogenetic relationships among 36 species of Argia Rambur, 1842, using complementary data sets (i.e., larval morphology and mitochondrial DNA). The morphological data set comprises 76% of the larvae currently described for this genus and includes 97 morphological characters. From those, 47 characters have not been previously used in taxonomic studies involving dragonflies’ larvae. This is the first cladistic study based on larvae morphology for species within the suborder Zygoptera. Data partitions were analyzed individually, as well as total evidence, using parsimony and Bayesian inference as criteria for optimal-tree selection. The results support the monophyly of the North American species of Argia. This genus can be identified by the combination of eight synapomorphies, four of which are exclusively found in Argia. According to the optimal trees, the individual data sets (i.e., morphology and DNA sequences) have a high level of homoplasy, resulting in soft polytomies and low support for several nodes. The specific relationships of the terminal units differ between the phylogenies; nonetheless, there is historical congruence among them. Within Argia, five clades were consistently recovered. Most of those clades have been identified, at least in part, in previous phylogenetic and taxonomic studies. Indubitably, the morphological characters from larvae have historical signal useful for cladistic and taxonomic inference. Therefore, it should be a priority to pay more attention to this source of characters.     

Implied weighting and its utility in palaeontological datasets: a study using modelled phylogenetic matrices

Implied weighting, a method for phylogenetic inference that actively seeks to downweight supposed homoplasy, has in recent years begun to be widely utilized in palaeontological datasets. Given the method's purported ability at handling widespread homoplasy/convergence, we investigate the effects of implied weighting on modelled phylogenetic data. We generated 100 character matrices consisting of 55 characters each using a Markov Chain morphology model of evolution based on a known phylogenetic tree. Rates of character evolution in these datasets were variable and generated by pulling from a gamma distribution for each character in the matrix. These matrices were then analysed under equal weighting and four settings of implied weights (k = 1, 3, 5, and 10). Our results show that implied weighting is inconsistent in its ability to retrieve a known phylogenetic tree. Equally weighted analyses are found to generally be more conservative, retrieving higher frequency of polytomies but being less likely to generate erroneous topologies. Implied weighting is found to generally resolve polytomies while also propagating errors, resulting in an increase in both correctly and incorrectly resolved nodes with a tendency towards higher rates of error compared to equal weighting. Our results suggest that equal weights may be a preferable method for parsimony analysis.     

Polytomies and Bayesian phylogenetic inference

Bayesian phylogenetic analyses are now very popular in systematics and molecular evolution because they allow the use of much more realistic models than currently possible with maximum likelihood methods. There are, however, a growing number of examples in which large Bayesian posterior clade probabilities are associated with very short branch lengths and low values for non-Bayesian measures of support such as nonparametric bootstrapping. For the four-taxon case when the true tree is the star phylogeny, Bayesian analyses become increasingly unpredictable in their preference for one of the three possible resolved tree topologies as data set size increases. This leads to the prediction that hard (or near-hard) polytomies in nature will cause unpredictable behavior in Bayesian analyses, with arbitrary resolutions of the polytomy receiving very high posterior probabilities in some cases. We present a simple solution to this problem involving a reversible-jump Markov chain Monte Carlo (MCMC) algorithm that allows exploration of all of tree space, including unresolved tree topologies with one or more polytomies. The reversible-jump MCMC approach allows prior distributions to place some weight on less-resolved tree topologies, which eliminates misleadingly high posteriors associated with arbitrary resolutions of hard polytomies. Fortunately, assigning some prior probability to polytomous tree topologies does not appear to come with a significant cost in terms of the ability to assess the level of support for edges that do exist in the true tree. Methods are discussed for applying arbitrary prior distributions to tree topologies of varying resolution, and an empirical example showing evidence of polytomies is analyzed and discussed.     

PROBLEMS WITH "SOFT" POLYTOMIES

Abstract— The "soft" assumption attributes polytomies to lack of data, not simultaneous cladogenesis (the "hard" assumption). Most systematists prefer the first interpretation, but most parsimony programs implicitly use the second. Results can thus be inconsistent with initial assumptions. Under certain circumstances that seem especially typical for large data sets treating higher taxa, it may be valid to eliminate both compatible and incompatible polytomous trees from consideration. Consistent treatment of soft polytomies can reduce the ambiguity of cladistic solutions and improve the resolution, and testability, of phylogenetic hypotheses.     

Testing character correlation using pairwise comparisons on a phylogeny

In comparative biology, pairwise comparisons of species or genes (terminal taxa) are used to detect character associations. For instance, if pairs of species contrasting in the state of a particular character are examined, the member of a pair with a particular state might be more likely than the other member to show a particular state in a second character. Pairs are chosen so as to be phylogenetically separate, that is, the path between members of a pair, along the branches of the tree, does not touch the path of any other pair. On a given phylogenetic tree, pairs must be chosen carefully to achieve the maximum possible number of pairs while maintaining phylogenetic separation. Many alternative sets of pairs may have this maximum number. Algorithms are developed that find all taxon pairings that maximize the number of pairs without constraint, or with the constraint that members of each pair have contrasting states in a binary character, or that they have contrasting states in two binary characters. The comparisons chosen by these algorithms, although phylogenetically separate on the tree, are not necessarily statistically independent.     

A first phylogenetic analysis of the pill millipedes of the order Glomerida,with a special assessment of mandible characters (Myriapoda,Diplopoda, Pentazonia)

The pill millipedes of the order Glomerida are a moderately diverse group with a classical Holarctic distribution pattern. Their classification is based on a typological system utilizing mainly a single character complex, the male telopods. In order to infer the apomorphies of the Glomerida, to elucidate its position in the Pentazonia, and to test the monophyly of its families and subfamilies, we conduct the first phylogenetic analysis of the order. To provide additional characters, we comparatively analyze the mandible using scanning electron microscopy. The final character matrix consists of 69 characters (11 mandible characters) and incorporates 22 species from 20 of the 34 pill millipede genera, representing all families and subfamilies, except the monotypic Mauriesiinae. Two species from each of the two other Pentazonian orders Sphaerotheriida and Glomeridesmida, as well as two Spirobolida, are included as outgroup taxa. The Glomerida are recovered as monophyletic and are supported by five apomorphies. Within the Pentazonia, the Glomeridesmida are recovered as the sister group to the classical Oniscomorpha (Sphaerotheriida + Glomerida) with weak support. The analysis provides little resolution within the Glomerida, resulting in numerous polytomies. Further morphological characters and/or the addition of molecular analyses are needed to produce a robust phylogenetic classification of the Glomerida.     

Word sense disambiguation in the biomedical domain: an overview.

There is a trend towards automatic analysis of large amounts of literature in the biomedical domain. However, this can be effective only if the ambiguity in natural language is resolved. In this paper, the current state of research in word sense disambiguation (WSD) is reviewed. Several methods for WSD have already been proposed, but many systems have been tested only on evaluation sets of limited size. There are currently only very few applications of WSD in the biomedical domain. The current direction of research points towards statistically based algorithms that use existing curated data and can be applied to large sets of biomedical literature. There is a need for manually tagged evaluation sets to test WSD algorithms in the biomedical domain. WSD algorithms should preferably be able to take into account both known and unknown senses of a word. Without WSD, automatic metaanalysis of large corpora of text will be error prone.     

Continuous characters analyzed as such

Quantitative and continuous characters have rarely been included in cladistic analyses of morphological data; when included, they have always been discretized, using a variety of ad hoc methods. As continuous characters are typically additive, they can be optimized with well known algorithms, so that with a proper implementation they could be easily analyzed without discretization. The program TNT has recently incorporated algorithms for analysis of continuous characters. One of the problems that has been pointed out with existing methods for discretization is that they can attribute different states to terminals that do not differ significantly—or vice versa. With the implementation in TNT, this problem is diminished (or avoided entirely) by simply assigning to each terminal a range that goes from the mean minus one (or two) SE to the mean plus one (or two) SE; given normal distributions, terminals that do not overlap thus differ significantly (more significantly if using more than 1 SE). Three real data sets (for scorpions, spiders and lizards) comprising both discrete and quantitative characters are analyzed to study the performance of continuous characters. One of the matrices has a reduced number of continuous characters, and thus continuous characters analyzed by themselves produce only poorly resolved trees; the support for many of the groups supported by the discrete characters alone, however, is increased when the continuous characters are added to the analysis. The other two matrices have larger numbers of continuous characters, so that the results of separate analyses for the discrete and the continuous characters can be more meaningfully compared. In both cases, the continuous characters (analyzed alone) result in trees that are relatively similar to the trees produced by the discrete characters alone. These results suggest that continuous characters carry indeed phylogenetic information, and that (if they have been observed) there is no real reason to exclude them from the analysis. © The Willi Hennig Society 2006.