子树分析和TASS程序及其在锦鸡儿属植物中的应用

子树分析和三分法 (TASS)程序是历史生物地理学中分布区关系的一种分析途径。它以分类群分支图为基础 ,以剔除其中分布区关系相悖理的结点并确定具信息的子树为目标 ,以便更有效地利用分布区信息。对分布区关系可以用若干子树和一个分布区分支图来表示。对锦鸡儿属 (Caragana)植物 72种和 13个分布区的子树分析和TASS程序运算后 ,得到 7个具信息的子树 ,它们分别表达了锦鸡儿属属内组、系所具有的分布区关系。属的分布区分支图也表达了 13个分布区的关系。与以前我们对本属成分分析的结果相吻合。     

ubtree,TASS and an Analysis of the Genus Caragana

Subtree analysis and three area satements (TASS) procedure are used to deal with the area relationship in historical biogeography. On the basis of the taxon cladogram, the procedure could identify and eliminate the paralogy node and determine the informative subtree. The area relationships are generally illustrated in several subtrees and the consensus tree. The distribution pattern of the genus Caragana comprising about 72 species and occurring in 13 areas, was analyzed by using subtree method and TASS procedure in this study. The results showed seven subtrees representing the area relationships of section and series of the genus, and the consensus tree provided the 13 area relationships. These results are congruent with our former result using component analysis for Caragana.     

Beyond pairwise distances: neighbor-joining with phylogenetic diversity estimates

The "neighbor-joining algorithm" is a recursive procedure for reconstructing trees that is based on a transformation of pairwise distances between leaves. We present a generalization of the neighbor-joining transformation, which uses estimates of phylogenetic diversity rather than pairwise distances in the tree. This leads to an improved neighbor-joining algorithm whose total running time is still polynomial in the number of taxa. On simulated data, the method outperforms other distance-based methods. We have implemented neighbor-joining for subtree weights in a program called MJOIN which is freely available under the Gnu Public License at http://bio.math.berkeley.edu/mjoin/.     

A fast GPU-based hybrid algorithm for addition chains

A graphics processing unit (GPU) has been widely used to accelerate discrete optimization problems. In this paper, we introduce a novel hybrid parallel algorithm to generate a shortest addition chain for a positive integer e. The main idea of the proposed algorithm is to divide the search tree into a sequence of three subtrees: top, middle, and bottom. The top subtree works using a branch and bound depth first strategy. The middle subtree works using a branch and bound breadth first strategy, while the bottom subtree works using a parallel (GPU) branch and bound depth first strategy. Our experimental results show that, compared to the fastest sequential algorithm for generating a shortest addition chain, we improve the generation by about 70% using one GPU (NVIDIA GeForce GTX 770). For generating all shortest addition chains, the percentage of the improvement is about 50%.     

All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees

Objective

In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees.

Results

Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it.

Conclusion

The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks.

     

BIMLR: A method for constructing rooted phylogenetic networks from rooted phylogenetic trees

Rooted phylogenetic trees constructed from different datasets (e.g. from different genes) are often conflicting with one another, i.e. they cannot be integrated into a single phylogenetic tree. Phylogenetic networks have become an important tool in molecular evolution, and rooted phylogenetic networks are able to represent conflicting rooted phylogenetic trees. Hence, the development of appropriate methods to compute rooted phylogenetic networks from rooted phylogenetic trees has attracted considerable research interest of late. The C_ASS algorithm proposed by van Iersel et al. is able to construct much simpler networks than other available methods, but it is extremely slow, and the networks it constructs are dependent on the order of the input data. Here, we introduce an improved C_ASS algorithm, BIMLR. We show that BIMLR is faster than C_ASS and less dependent on the input data order. Moreover, BIMLR is able to construct much simpler networks than almost all other methods. BIMLR is available at http://nclab.hit.edu.cn/wangjuan/BIMLR/.     

A Combinatorial Approach to Detect Coevolved Amino Acid Networks in Protein Families of Variable Divergence

Communication between distant sites often defines the biological role of a protein: amino acid long-range interactions are as important in binding specificity, allosteric regulation and conformational change as residues directly contacting the substrate. The maintaining of functional and structural coupling of long-range interacting residues requires coevolution of these residues. Networks of interaction between coevolved residues can be reconstructed, and from the networks, one can possibly derive insights into functional mechanisms for the protein family. We propose a combinatorial method for mapping conserved networks of amino acid interactions in a protein which is based on the analysis of a set of aligned sequences, the associated distance tree and the combinatorics of its subtrees. The degree of coevolution of all pairs of coevolved residues is identified numerically, and networks are reconstructed with a dedicated clustering algorithm. The method drops the constraints on high sequence divergence limiting the range of applicability of the statistical approaches previously proposed. We apply the method to four protein families where we show an accurate detection of functional networks and the possibility to treat sets of protein sequences of variable divergence.     

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.     

Ontogenetic wood anatomy of tree and subtree species of Nepalese Rhododendron (Ericaceae) and characterization of shrub species

Ontogenetic trends in the wood structure of Nepalese Rhododendron were studied in 15 specimens of two tree and four subtree species. Average growth ring width was constant from pith to bark in spite of occurrences of extremely narrow, false, or discontinuous rings. Vessel density, vessel area, vessel element length, and multiseriate ray height generally had an initial increase or decrease to 1.5 cm radius and near plateau or slight decrease or increase outward. Multiseriate ray density and area percentage were variable between specimens without a clear pattern. Ontogenetic trends from pith to fully mature wood in trees plus subtrees were inferred by treating the measurements in the present study with those of mature individuals in a previous study. Comparison of trends in trees plus subtrees and those in shrubs lead to ecological or systematic groupings. Vessel features showed that alpine shrub species have distinctly small, numerous vessels composed of short vessel elements. Multiseriate ray features indicated a systematic difference between the trees plus subtrees of subgenus Hymenanthes and the shrubs of subgenus Rhododendron. Vessel features of alpine shrubs may be an adaptation against frequent freeze-thaw cycles or the result of growth stress imposed by the severe alpine environment.     

Counting glycans revisited

We present an algorithm for counting glycan topologies of order \(n\) that improves on previously described algorithms by a factor \(n\) in both time and space. More generally, we provide such an algorithm for counting rooted or unrooted \(d\) -ary trees with labels or masses assigned to the vertices, and we give a “recipe” to estimate the asymptotic growth of the resulting sequences. We provide constants for the asymptotic growth of \(d\) -ary trees and labeled quaternary trees (glycan topologies). Finally, we show how a classical result from enumeration theory can be used to count glycan structures where edges are labeled by bond types. Our method also improves time bounds for counting alkanes.     

A quantitative structure-activity relationship (QSAR) study on glycan array data to determine the specificities of glycan-binding proteins

Advances in glycan array technology have provided opportunities to automatically and systematically characterize the binding specificities of glycan-binding proteins. However, there is still a lack of robust methods for such analyses. In this study, we developed a novel quantitative structure-activity relationship (QSAR) method to analyze glycan array data. We first decomposed glycan chains into mono-, di-, tri- or tetrasaccharide subtrees. The bond information was incorporated into subtrees to help distinguish glycan chain structures. Then, we performed partial least-squares (PLS) regression on glycan array data using the subtrees as features. The application of QSAR to the glycan array data of different glycan-binding proteins demonstrated that PLS regression using subtree features can obtain higher R(2) values and a higher percentage of variance explained in glycan array intensities. Based on the regression coefficients of PLS, we were able to effectively identify subtrees that indicate the binding specificities of a glycan-binding protein. Our approach will facilitate the glycan-binding specificity analysis using the glycan array. A user-friendly web tool of the QSAR method is available at http://bci.clemson.edu/tools/glycan_array.     

BMTK: a toolkit for determining modules in biological bipartite networks

Background: Module detection is widely used to analyze and visualize biological networks. A number of methods and tools have been developed to achieve it. Meanwhile, bipartite module detection is also very useful for mining and analyzing bipartite biological networks and a few methods have been developed for it. However, there is few user-friendly toolkit for this task. Methods: To this end, we develop an online web toolkit BMTK, which implements seven existing methods. Results: BMTK provides a uniform operation platform and visualization function, standardizes input and output format, and improves algorithmic structure to enhance computing speed. We also apply this toolkit onto a drug-target bipartite network to demonstrate its effectiveness. Conclusions: BMTK will be a powerful tool for detecting bipartite modules in diverse bipartite biological networks. Availability: The web application is freely accessible at the website of Zhang lab.     

Historical biogeography of Australian Rhamnaceae, tribe Pomaderreae

Aim To discover the pattern of relationships of areas of endemism for Australian genera in the plant family Rhamnaceae tribe Pomaderreae for comparison with other taxa and interpretation of biogeographical history. Location Australian mainland, Tasmania and New Zealand. Methods A molecular phylogeny and geographic distribution of species within four clades of Pomaderreae are used as a basis for recognition of areas of endemism and analysis of area relationships using paralogy‐free subtrees. The taxon phylogeny is the strict consensus tree from a parsimony analysis of 54 taxa, in four clades, and sequence data for the internal transcribed spacer regions of ribosomal DNA (ITS1‐5.8S‐ITS2) and the plastid DNA region trnL‐F. Results The biogeographical analysis identified five subtrees, which, after parsimony analysis, resulted in a minimal tree with 100% consistency and seven resolved nodes. Three sets of area relationships were identified: the areas of Arnhem and Kimberley in tropical north Australia are related based on the phylogeny of taxa within Cryptandra; the moister South‐west of Western Australia, its sister area the coastal Geraldton Sandplains, the semi‐arid Interzone region and arid Western Desert are related, based on taxa within Cryptandra, Spyridium, Trymalium and Pomaderris; and the eastern regions of Queensland, McPherson‐Macleay, south‐eastern New South Wales (NSW), Victoria, southern Australia, Tasmania and New Zealand are related based on Cryptandra, Pomaderris and Spyridium. Tasmania and NSW are related based entirely on Cryptandra, but the position of New Zealand relative to the other south‐eastern Australian regions is unresolved. Main conclusions The method of paralogy‐free subtrees identified a general pattern of geographic area relationships based on Australian Pomaderreae. The widespread distribution of clades, the high level of endemicity and the age of fossils for the family, suggest that the Pomaderreae are an old group among the Australian flora. Their biogeographical history may date to the early Palaeogene with subsequent changes through to the Pleistocene.     

On Hill et al's conjecture for calculating the subtree prune and regraft distance between phylogenies

Background  

Recently, Hill et al. [1] implemented a new software package--called SPRIT--which aims at calculating the minimum number of horizontal gene transfer events that is needed to simultaneously explain the evolution of two rooted binary phylogenetic trees on the same set of taxa. To this end, SPRIT computes the closely related so-called rooted subtree prune and regraft distance between two phylogenies. However, calculating this distance is an NP-hard problem and exact algorithms are often only applicable to small- or medium-sized problem instances. Trying to overcome this problem, Hill et al. propose a divide-and-conquer approach to speed up their algorithm and conjecture that this approach can be used to compute the rooted subtree prune and regraft distance exactly.     

Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs

SUMMARY: Biological and engineered networks have recently been shown to display network motifs: a small set of characteristic patterns that occur much more frequently than in randomized networks with the same degree sequence. Network motifs were demonstrated to play key information processing roles in biological regulation networks. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs with a given number of nodes in the network. The runtime of such algorithms increases strongly with network size. Here, we present a novel algorithm that allows estimation of subgraph concentrations and detection of network motifs at a runtime that is asymptotically independent of the network size. This algorithm is based on random sampling of subgraphs. Network motifs are detected with a surprisingly small number of samples in a wide variety of networks. Our method can be applied to estimate the concentrations of larger subgraphs in larger networks than was previously possible with exhaustive enumeration algorithms. We present results for high-order motifs in several biological networks and discuss their possible functions. AVAILABILITY: A software tool for estimating subgraph concentrations and detecting network motifs (mfinder 1.1) and further information is available at http://www.weizmann.ac.il/mcb/UriAlon/     

Neuron splitting in compute-bound parallel network simulations enables runtime scaling with twice as many processors

Neuron tree topology equations can be split into two subtrees and solved on different processors with no change in accuracy, stability, or computational effort; communication costs involve only sending and receiving two double precision values by each subtree at each time step. Splitting cells is useful in attaining load balance in neural network simulations, especially when there is a wide range of cell sizes and the number of cells is about the same as the number of processors. For compute-bound simulations load balance results in almost ideal runtime scaling. Application of the cell splitting method to two published network models exhibits good runtime scaling on twice as many processors as could be effectively used with whole-cell balancing.     

Biomolecular network motif counting and discovery by color coding

Protein-protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k < or = 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k > or = 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the 'color coding' technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G' with k vertices in a network G with n vertices in time polynomial with n, provided k = O(log n). We use our algorithm to obtain 'treelet' distributions for k < or = 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the 'duplication model' but are quite different from that of the 'preferential attachment model'. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%.     

Analytic solutions of maximum likelihood on forks of four taxa

This work deals with symbolic mathematical solutions to maximum likelihood on small phylogenetic trees. Maximum likelihood (ML) is increasingly used as an optimality criterion for selecting evolutionary trees, but finding the global optimum is a hard computational task. In this work, we give general analytic solutions for a family of trees with four taxa, two state characters, under a molecular clock. Previously, analytical solutions were known only for three taxa trees. The change from three to four taxa incurs a major increase in the complexity of the underlying algebraic system, and requires novel techniques and approaches. Despite the simplicity of our model, solving ML analytically in it is close to the limit of today's tractability. Four taxa rooted trees have two topologies--the fork (two subtrees with two leaves each) and the comb (one subtree with three leaves, the other with a single leaf). Combining the properties of molecular clock fork trees with the Hadamard conjugation, and employing the symbolic algebra software Maple, we derive a number of topology dependent identities. Using these identities, we substantially simplify the system of polynomial equations for the fork. We finally employ the symbolic algebra software to obtain closed form analytic solutions (expressed parametrically in the input data).     

Reconstructing evolution of sequences subject to recombination using parsimony

The parsimony principle states that a history of a set of sequences that minimizes the amount of evolution is a good approximation to the real evolutionary history of the sequences. This principle is applied to the reconstruction of the evolution of homologous sequences where recombinations or horizontal transfer can occur. First it is demonstrated that the appropriate structure to represent the evolution of sequences with recombinations is a family of trees each describing the evolution of a segment of the sequence. Two trees for neighboring segments will differ by exactly the transfer of a subtree within the whole tree. This leads to a metric between trees based on the smallest number of such operations needed to convert one tree into the other. An algorithm is presented that calculates this metric. This metric is used to formulate a dynamic programming algorithm that finds the most parsimonious history that fits a given set of sequences. The algorithm is potentially very practical, since many groups of sequences defy analysis by methods that ignore recombinations. These methods give ambiguous or contradictory results because the sequence history cannot be described by one phylogeny, but only a family of phylogenies that each describe the history of a segment of the sequences. The generalization of the algorithm to reconstruct gene conversions and the possibility for heuristic versions of the algorithm for larger data sets are discussed.     

Molecular clock fork phylogenies: closed form analytic maximum likelihood solutions

Maximum likelihood (ML) is increasingly used as an optimality criterion for selecting evolutionary trees, but finding the global optimum is a hard computational task. Because no general analytic solution is known, numeric techniques such as hill climbing or expectation maximization (EM) are used in order to find optimal parameters for a given tree. So far, analytic solutions were derived only for the simplest model-three-taxa, two-state characters, under a molecular clock. Quoting Ziheng Yang, who initiated the analytic approach,"this seems to be the simplest case, but has many of the conceptual and statistical complexities involved in phylogenetic estimation."In this work, we give general analytic solutions for a family of trees with four-taxa, two-state characters, under a molecular clock. The change from three to four taxa incurs a major increase in the complexity of the underlying algebraic system, and requires novel techniques and approaches. We start by presenting the general maximum likelihood problem on phylogenetic trees as a constrained optimization problem, and the resulting system of polynomial equations. In full generality, it is infeasible to solve this system, therefore specialized tools for the molecular clock case are developed. Four-taxa rooted trees have two topologies-the fork (two subtrees with two leaves each) and the comb (one subtree with three leaves, the other with a single leaf). We combine the ultrametric properties of molecular clock fork trees with the Hadamard conjugation to derive a number of topology dependent identities. Employing these identities, we substantially simplify the system of polynomial equations for the fork. We finally employ symbolic algebra software to obtain closed formanalytic solutions (expressed parametrically in the input data). In general, four-taxa trees can have multiple ML points. In contrast, we can now prove that each fork topology has a unique(local and global) ML point.