loading...
A Mutation-Sensitive Approach for Locating Conserved Gene Pairs between Related Species
Taichung, Taiwan, ROC May 19-May 21
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317390Fourth IEEE Symposium on Bioinformati ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
H. L. Chan, University of Hong Kong
T. W. Lam, University of Hong Kong
W. K. Sung, National University of Singapore
Prudence W. H. Wong, University of Hong Kong
S. M. Yiu, University of Hong Kong
This paper proposes a new approach for solving the whole genome alignment problem. Our approach is based on a new structural optimization problem (called the MUM Selection Problem) related to mutations via reversals and transpositions. We have devised a practical algorithm for this optimization problem and have evaluated the algorithm using 15 pairs of human and mouse chromosomes. The results show that our algorithm is both effective and efficient. More specifically, our algorithm can reveal 91% of the conserved gene pairs that have been reported in the literature. When compared to existing software MUMmer [Fast algorithms for large-scale genome alignment and comparison, http://www.tigr.org/software/mummer/] and MaxMinCluster [Efficient algorithms for optimizing whole genome alignment with noise], our algorithm uncovers 15% and 7% more genes on average, respectively. The sensitivity of our algorithm is also slightly higher. The paper concludes with a remark on the computational hardness of the MUM Selection Problem.
Index Terms:
whole genome alignment, conserved gene pairs, mutation
Citation:
H. L. Chan, T. W. Lam, W. K. Sung, Prudence W. H. Wong, S. M. Yiu, "A Mutation-Sensitive Approach for Locating Conserved Gene Pairs between Related Species," bibe, pp.545, Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.