title: Improved short adjacent repeat identification using three evolutionary Monte Carlo schemes.
abstract: This paper employs three Evolutionary Monte Carlo (EMC) schemes to solve the Short Adjacent Repeat Identification Problem (SARIP), which aims to identify the common repeat units shared by multiple sequences. The three EMC schemes, i.e., Random Exchange (RE), Best Exchange (BE), and crossover are implemented on a parallel platform. The simulation results show that compared with the conventional Markov Chain Monte Carlo (MCMC) algorithm, all three EMC schemes can not only shorten the computation time via speeding up the convergence but also improve the solution quality in difficult cases. Moreover, we observe that the performances of different EMC schemes depend on the degeneracy degree of the motif pattern.
authors.affiliation: Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong. xujin@eee.hku.hk
authors.forename: Jin
authors.initials: J
authors.lastname: Xu
authors.affiliation: Department of Statistics, The Chinese University of Hong Kong, Sha Tin, Hong Kong.
authors.forename: Qiwei
authors.initials: Q
authors.lastname: Li
authors.affiliation: Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong.
authors.forename: Victor O K
authors.initials: VO
authors.lastname: Li
authors.affiliation: Department of Information Engineering, The Chinese University of Hong Kong, Sha Tin, Hong Kong.
authors.forename: Shuo-Yen Robert
authors.initials: SY
authors.lastname: Li
authors.affiliation: Department of Statistics, The Chinese University of Hong Kong, Sha Tin, Hong Kong.
authors.forename: Xiaodan
authors.initials: X
authors.lastname: Fan
mesh_terms: D000465:Algorithms; D008390:Markov Chains; D018895:Microsatellite Repeats; D009010:Monte Carlo Method; D010363:Pattern Recognition, Automated