Short adjacent repeat identification based on Chemical Reaction Optimization

摘要: The analysis of short tandem repeats (STRs) in DNA sequences has become an attractive method for determining the genetic profile individual. Here we focus on a more general and practical issue named adjacent identification problem (SARIP), which is extended from STR by allowing gaps between neighboring units. Presently, best available solution to SARIP BASARD, uses Markov chain Monte Carlo algorithms determine posterior estimate. However, computational complexity tendency get stuck local mode lower efficiency BASARD impede its wide application. In this paper, prove that NP-hard, also solve it with Chemical Reaction Optimization (CRO), recently developed metaheuristic approach. CRO mimics interactions molecules chemical reaction can explore space efficiently find optimal or near solution(s). We test algorithm both synthetic real data, compare performance searching BASARD. Simulation results show enjoys dozens times, even hundred times shorter time compared It demonstrated obtain global optima most time. Moreover, stable different runs, great importance use. Thus, far SARIP.