Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE'04)
A Mutation-Sensitive Approach for Locating Conserved Gene Pairs between Related Species
Taichung, Taiwan, ROC
May 19-May 21
ISBN: 0-7695-2173-8
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