tailieunhanh - Ant Colony Optimization based Founder Sequence Reconstruction

In this paper we propose an ant colony optimization algorithm (ACO) based method, equipped with some important improvements, for the founder DNA sequence reconstruction problem. The proposed method yields excellent performance when validating on 108 test sets from three benchmark datasets. Comparing with the best by far corresponding method, our proposed method performs better in 45 test sets, equally well in 44 and worse only in 19 sets. These experimental results demonstrate the efficacy and perspective of our proposed method. | VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65 Ant Colony Optimization based Founder Sequence Reconstruction Anh Vu Thi Ngoc1, Dinh Phuc Thai2, Hoang Duc Nguyen2, Thanh Hai Dang2,∗, Dong Do Duc2 1The 2Faculty Hanoi college of Industrial Economics of Information Technology, VNU University of Engineering and Technology Abstract Reconstruction of a set of genetic sequences (founders) that can combine together to form given genetic sequences (. DNA) of individuals of a population is an important problem in evolutionary biology. Such reconstruction can be modeled as a combinatorial optimization problem, in which we have to find a set of founders upon that genetic sequences of the population can be generated using a smallest number of recombinations. In this paper we propose an ant colony optimization algorithm (ACO) based method, equipped with some important improvements, for the founder DNA sequence reconstruction problem. The proposed method yields excellent performance when validating on 108 test sets from three benchmark datasets. Comparing with the best by far corresponding method, our proposed method performs better in 45 test sets, equally well in 44 and worse only in 19 sets. These experimental results demonstrate the efficacy and perspective of our proposed method. Received 11 Sep 2017; Revised 31 Dec 2017; Accepted 31 Dec 2017 Keywords: Founder sequence reconstruction (FSR), Ancestor genes, Ant colony optimization (ACO). * To this end, the main challenge is at the problem of determining the plausible number of founder (ancestor) sequences and of finding themselves for a given finite offspring sequences. It is well known as the founder sequence reconstruction problem. Various methods have been recently proposed for reconstructing founder sequences, such as those based on dynamic programming [2], tree search [3], neighboring search [4] and metaheuristics [5]. In this paper we propose a ant colony optimization (ACO) based .