Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (3 results)

  • Thesis
  • Peer Reviewed
UC Riverside Electronic Theses and Dissertations (2011)

The accurate identification of orthologous genes across different species is a critical and challenging problem in comparative genomics and has a wide spectrum of biological applications including gene function inference, evolutionary studies and systems biology. During the past several years, many methods have been proposed for ortholog assignment based on sequence similarity, phylogenetic approaches, synteny information, and genome rearrangement. Although these methods share many commonly assigned orthologs, each method tends to produce an ortholog assignment significantly different from the others.

In this dissertation, we study the problem of assigning orthologous genes among closely related genomes on a genome scale. We first give a brief review of the existing methods for ortholog assignment in the literature, followed by a comprehensive comparison of each method. We then propose a new combinatorial approach for assigning ortholog pairs between a pair of closely related genomes by addressing the limitations of the existing methods. Our approach is based on the parsimony principle to transform one genome to another by minimizing the number of genome rearrangement events, including reversal, transposition, fusion, fission and gene duplications. By explicitly incorporating tandem gene duplication model and combining phylogenetic approaches, we develop an improved system MSOAR 2.0. Our experimental results on both simulated data and real data show that MSOAR 2.0 achieves the highest overall prediction accuracy among different programs in comparison.

Based on pairwise genome comparison results, we extend our ortholog assignment method to multiple genome comparison and develop a new system MultiMSOAR 2.0 to identify ortholog groups among multiple genomes. In MultiMSOAR 2.0, pairwise orthology information produced by MSOAR 2.0 is used to construct multipartite graphs for each gene family. In order to partition each gene family into a set of disjoint sets of orthologous genes, a multidimensional matching problem is formulated and a heuristic maximum weight matching algorithm is proposed. The partition results are then used to label the species tree. Considering some biological constraints, we formulate the tree labeling problem in the combinatorial optimization framework and develop two dynamic programming algorithms to solve the problem. Our experimental results show that MultiMSOAR 2.0 achieves much higher prediction accuracy than the existing ortholog assignment systems for multiple genomes. Moreover, MultiMSOAR 2.0 also provides information about gene births, duplications and losses in evolution, which may be of independent biological interest.

    Cover page: Combinatorial Approaches to Accurate Identification of Orthologous Genes
    • Article
    • Peer Reviewed
    UC Riverside Previously Published Works (2010)

    Background

    Ortholog assignment is a critical and fundamental problem in comparative genomics, since orthologs are considered to be functional counterparts in different species and can be used to infer molecular functions of one species from those of other species. MSOAR is a recently developed high-throughput system for assigning one-to-one orthologs between closely related species on a genome scale. It attempts to reconstruct the evolutionary history of input genomes in terms of genome rearrangement and gene duplication events. It assumes that a gene duplication event inserts a duplicated gene into the genome of interest at a random location (i.e., the random duplication model). However, in practice, biologists believe that genes are often duplicated by tandem duplications, where a duplicated gene is located next to the original copy (i.e., the tandem duplication model).

    Results

    In this paper, we develop MSOAR 2.0, an improved system for one-to-one ortholog assignment. For a pair of input genomes, the system first focuses on the tandemly duplicated genes of each genome and tries to identify among them those that were duplicated after the speciation (i.e., the so-called inparalogs), using a simple phylogenetic tree reconciliation method. For each such set of tandemly duplicated inparalogs, all but one gene will be deleted from the concerned genome (because they cannot possibly appear in any one-to-one ortholog pairs), and MSOAR is invoked. Using both simulated and real data experiments, we show that MSOAR 2.0 is able to achieve a better sensitivity and specificity than MSOAR. In comparison with the well-known genome-scale ortholog assignment tool InParanoid, Ensembl ortholog database, and the orthology information extracted from the well-known whole-genome multiple alignment program MultiZ, MSOAR 2.0 shows the highest sensitivity. Although the specificity of MSOAR 2.0 is slightly worse than that of InParanoid in the real data experiments, it is actually better than that of InParanoid in the simulation tests.

    Conclusions

    Our preliminary experimental results demonstrate that MSOAR 2.0 is a highly accurate tool for one-to-one ortholog assignment between closely related genomes. The software is available to the public for free and included as online supplementary material.
      Cover page: MSOAR 2.0: Incorporating tandem duplications into ortholog assignment based on genome rearrangement
      • Article
      • Peer Reviewed
      UC Riverside Previously Published Works (2011)
      The identification of orthologous genes shared by multiple genomes plays an important role in evolutionary studies and gene functional analyses. Based on a recently developed accurate tool, called MSOAR 2.0, for ortholog assignment between a pair of closely related genomes based on genome rearrangement, we present a new system MultiMSOAR 2.0, to identify ortholog groups among multiple genomes in this paper. In the system, we construct gene families for all the genomes using sequence similarity search and clustering, run MSOAR 2.0 for all pairs of genomes to obtain the pairwise orthology relationship, and partition each gene family into a set of disjoint sets of orthologous genes (called super ortholog groups or SOGs) such that each SOG contains at most one gene from each genome. For each such SOG, we label the leaves of the species tree using 1 or 0 to indicate if the SOG contains a gene from the corresponding species or not. The resulting tree is called a tree of ortholog groups (or TOGs). We then label the internal nodes of each TOG based on the parsimony principle and some biological constraints. Ortholog groups are finally identified from each fully labeled TOG. In comparison with a popular tool MultiParanoid on simulated data, MultiMSOAR 2.0 shows significantly higher prediction accuracy. It also outperforms MultiParanoid, the Roundup multi-ortholog repository and the Ensembl ortholog database in real data experiments using gene symbols as a validation tool. In addition to ortholog group identification, MultiMSOAR 2.0 also provides information about gene births, duplications and losses in evolution, which may be of independent biological interest. Our experiments on simulated data demonstrate that MultiMSOAR 2.0 is able to infer these evolutionary events much more accurately than a well-known software tool Notung. The software MultiMSOAR 2.0 is available to the public for free.
        Cover page: MultiMSOAR 2.0: An Accurate Tool to Identify Ortholog Groups among Multiple Genomes
        Top