Paper Info
Title
Evolutionary metropolis sampling in sequence alignment space
Abstract
Metropolis sampling is the earliest Markov chain Monte Carlo (MCMC) method and MCMC has been widely used in motif-finding via sequence local alignment. A key issue in the design of MCMC algorithms is to improve the proposal mechanism and the mixing behavior. To overcome these difficulties, it is common either to run a population of chains or incorporate the evolutionary computing techniques into the MCMC framework. This paper combines a simple evolutionary (genetic) algorithm (GA) with the metropolis sampler and proposes the new motif algorithm GAMS to carry out motif heuristic search throughout the multiple alignment space. GAMS first initializes a population of multiple local alignments (initial MCMC chains) each of which is encoded on a chromosome that represents a potential solution. GAMS then conducts a genetic algorithm-based search in the sequence alignment space using a motif scoring function as the fitness measure. The genetic algorithm gradually moves this population towards the best alignment from which the motif model is derived. Experimental results show that the new algorithm compares favorably to the simple multiple-run MCMC in some difficult cases, and it also exhibits higher precision than some popular motif-finding algorithms while testing on the annotated prokaryotic and eukaryotic binding sites data sets.
Year
DOI
Venue
2008
10.1109/CEC.2008.4630797
IEEE Congress on Evolutionary Computation
Keywords
Field
DocType
motif scoring function,evolutionary computing techniques,prokaryotic binding sites data sets,motif heuristic search,motif-finding,sequences,genetic algorithm,markov chain monte carlo method,monte carlo methods,genetic algorithms,sequence local alignment space,sampling methods,markov processes,eukaryotic binding sites data sets,evolutionary metropolis sampling,bioinformatics,evolutionary genetics,proteins,score function,genetics,gene expression,multiple alignment,genomics,computational modeling,evolutionary computing,heuristic search,markov chain monte carlo,dna,sequence alignment,machinery,gallium,binding site,local alignment,bismuth
Population,Heuristic,Markov process,Markov chain Monte Carlo,Computer science,Evolutionary computation,Artificial intelligence,Smith–Waterman algorithm,Multiple sequence alignment,Genetic algorithm,Machine learning
Conference
ISBN
Citations 
PageRank 
978-1-4244-1823-7
5
0.44
References 
Authors
13
1
Name
Order
Citations
PageRank
Chengpeng Bi113111.29