Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2010, Vol. 25 Issue (1) :42-52    DOI:
Special Issue on Computational Challenges from Modern Molecular Biology Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Some Algorithmic Challenges in Genome-Wide Ortholog Assignment
Tao Jiang (姜涛), Fellow, ACM
Department of Computer Science and Engineering, University of California, Riverside, CA 92521, U.S.A.
School of Information Science and Technology, Tsinghua University, Beijing 100084, China

Related Articles
Download: [PDF 355KB]     Export: BibTeX or EndNote (RIS)  

Genome-scale assignment of orthologous genes is a fundamental and challenging problem in computational biology and has a wide range of applications in comparative genomics, functional genomics, and systems biology. Many methods based on sequence similarity, phylogenetic analysis, chromosomal syntenic information, and genome rearrangement have been proposed in recent years for ortholog assignment. Although these methods produce results that largely agree with each other, their results may still contain significant differences. In this article, we consider the recently proposed parsimony approach for assigning orthologs between closely related genomes based on genome rearrangement, which essentially attempts to transform one genome into another by the smallest number of genome rearrangement events including reversal, translocation, fusion, and fission, as well as gene duplication events. We will highlight some of the challenging algorithmic problems that arise in the approach including (i) minimum common substring partition, (ii) signed reversal distance with duplicates, and (iii) signed transposition distance with duplicates. The most recent progress towards the solution of these problems will be reviewed and some open questions will be posed. We will also discuss some possible extensions of the approach to the simultaneous comparison of multiple genomes.

Articles by authors
Tao Jiang
Keywordsalgorithm    comparative genomics    computational biology    genome rearrangement    ortholog assignment     
Received 2009-09-01;

This work is supported by the NSF of USA under Grant No. IIS-0711129.

Cite this article:   
Tao Jiang, Fellow, ACM.Some Algorithmic Challenges in Genome-Wide Ortholog Assignment[J]  Journal of Computer Science and Technology, 2010,V25(1): 42-52
Copyright 2010 by Journal of Computer Science and Technology