Chan H L, Lam T W, Sung W K, Wong Prudence W H, Yiu S M, Fan X
Department of Computer Science, University of Hong Kong, Hong Kong, China.
Bioinformatics. 2005 May 15;21(10):2271-8. doi: 10.1093/bioinformatics/bti371. Epub 2005 Mar 3.
For the purpose of locating conserved genes in a whole genome scale, this paper proposes a new structural optimization problem called the Mutated Subsequence Problem, which gives consideration to possible mutations between two species (in the form of reversals and transpositions) when comparing the genomes.
A practical algorithm called mutated subsequence algorithm (MSS) is devised to solve this optimization problem, and it has been evaluated using different pairs of human and mouse chromosomes, and different pairs of virus genomes of Baculoviridae. MSS is found to be effective and efficient; in particular, MSS can reveal >90% of the conserved genes of human and mouse that have been reported in the literature. When compared with existing softwares MUMmer and MaxMinCluster, MSS uncovers 14 and 7% more genes on average, respectively. Furthermore, this paper shows a hybrid approach to integrate MUMmer or MaxMinCluster with MSS, which has better performance and reliability.
为了在全基因组规模上定位保守基因，本文提出了一个新的结构优化问题，称为突变子序列问题，该问题在比较基因组时考虑了两个物种之间可能的突变（以反转和转座的形式）。
设计了一种名为突变子序列算法（MSS）的实用算法来解决此优化问题，并使用不同的人类和小鼠染色体对以及杆状病毒科的不同病毒基因组对进行了评估。发现MSS是有效且高效的；特别是，MSS可以揭示文献中报道的人类和小鼠>90%的保守基因。与现有软件MUMmer和MaxMinCluster相比，MSS平均分别多发现14%和7%的基因。此外，本文展示了一种将MUMmer或MaxMinCluster与MSS集成的混合方法，该方法具有更好的性能和可靠性。
