Cyclic permutations and evolutionary trees

Given a tree with leaf set X, there are certain ways of arranging the elements of X in a circular order so that can be embedded in the plane and ‘preserve’ this ordering. We investigate some new combinatorial properties of these ‘circular orderings.’ We then use these properties to establish two results concerning dissimilarity maps on X that are induced by edge-weighted trees with leaf set X.     

Parametric multiple sequence alignment and phylogeny construction

Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual formulations of these problems fall within the same integer parametric framework, implying that the number of distinct optima obtained as the parameters are varied across their ranges is polynomially bounded in the length and number of sequences.     

Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.     

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

Structural insights of a cellobiose dehydrogenase enzyme from the basidiomycetes fungus Termitomyces clypeatus

Filamentous fungi secrete various oxidative enzymes to degrade the glycosidic bonds of polysaccharides. Cellobiose dehydrogenase (CDH) (E.C.1.1.99.18) is one of the important lignocellulose degrading enzymes produced by various filamentous fungi. It contains two stereo specific ligand binding domains, cytochrome and dehydrogenase - one for heme and the other for flavin adenine dinucleotide (FAD) respectively. The enzyme is of commercial importance for its use in amperometric biosensor, biofuel production, lactose determination in food, bioremediation etc. Termitomyces clypeatus, an edible fungus belonging to the basidiomycetes group, is a good producer of CDH. In this paper we have analyzed the structural properties of this enzyme from T. clypeatus and identified a distinct carbohydrate binding module (CBM) which is not present in most fungi belonging to the basidiomycetes group. In addition, the dehydrogenase domain of T. clypeatus CDH exhibited the absence of cellulose binding residues which is in contrast to the dehydrogenase domains of CDH of other basidiomycetes. Sequence analysis of cytochrome domain showed that the important residues of this domain were conserved like in other fungal CDHs. Phylogenetic tree, constructed using basidiomycetes and ascomycetes CDH sequences, has shown that very surprisingly the CDH from T. clypeatus, which is classified as a basidiomycetes fungus, is clustered with the ascomycetes group. A homology model of this protein has been constructed using the CDH enzyme of ascomycetes fungus Myricoccum thermophilum as a template since it has been found to be the best match sequence with T. clypeatus CDH. We also have modelled the protein with its substrate, cellobiose, which has helped us to identify the substrate interacting residues (L354, P606, T629, R631, Y649, N732, H733 and N781) localized within its dehydrogenase domain. Our computational investigation revealed for the first time the presence of all three domains - cytochrome, dehydrogenase and CBM - in the CDH of T. clypeatus, a basidiomycetes fungus. In addition to discovering the unique structural attributes of this enzyme from T. clypeatus, our study also discusses the possible phylogenetic status of this fungus.     

Identification of functional divergence sites in dopamine receptors of vertebrates

Dopamine is one of the major neurotransmitters in the brain and body, and regulates a wide variety of functions via its binding with dopamine receptors. Abnormalities in dopamine receptors have also been found to be related to various neurological disorders. For such reason, dopamine receptors are among the key components to understanding the molecular mechanisms of many diseases, they are also the potential drug targets for the treatment of many diseases. Till now, five different dopamine receptors (D1-D5) have been identified in mammals, which are assumed to be evolved from a common ancestor after multiple gene duplication events and functional divergence. Thus, identifying the specific features of each dopamine receptor, will not only provide clues for understanding the functional differences between the receptors, but also help us to design drugs specific for a certain subtype of receptor. In this study, we investigated the functional divergence in dopamine receptors in representative vertebrate species by analyzing their molecular evolution features. Our results showed that the coefficients for type I functional divergence (θ_I) were significantly greater than 0 for all the pairwise comparisons between the five dopamine receptors, suggesting that type I functional divergence, i.e., altered functional constraints or different evolutionary rates, may have taken place at some amino acids in the receptors. We further identified 84 potential type I functional divergence peptide sites for the pairwise comparisons between the D1-like and D2-like are identified in total. When these sites were mapped to the 3D structure of dopamine receptors, most of them were included in ICL3, M6 and M7 domains. Especially, sixteen of these sites may be the major sites associated with the changes of properties between D1-like and D2-like receptors. These sites provide molecular basis for further studies such as dopamine receptor function exploration and subtype specific drug design and screening.     

An alignment-free measure based on physicochemical properties of amino acids for protein sequence comparison

Sequence comparison is an important topic in bioinformatics. With the exponential increase of biological sequences, the traditional protein sequence comparison methods — the alignment methods become limited, so the alignment-free methods are widely proposed in the past two decades. In this paper, we considered not only the six typical physicochemical properties of amino acids, but also their frequency and positional distribution. A 51-dimensional vector was obtained to describe the protein sequence. We got a pairwise distance matrix by computing the standardized Euclidean distance, and discriminant analysis and phylogenetic analysis can be made. The results on the Influenza A virus and ND5 datasets indicate that our method is accurate and efficient for classifying proteins and inferring the phylogeny of species.