Ant colony optimization based founder sequence reconstruction
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 Nguyen , Thanh Hai Dang , Dong Do Duc
2
2,
2
∗
1The Hanoi college of Industrial Economics
2Faculty 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 (e.g. 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).
*1. Introduction
To this end, the main challenge is at the
problem of determining the plausible number of
founder (ancestor) sequences and of finding
Today we have been observing a huge
amount
of
biological
sequences
themselves for
a
given finite offspring
(e.g. DNA/genes, proteins) steadily being
generated thanks to the unprecedentedly fast
development of bio-technologies. Having
genetic sequences of a population, researchers
are often interested in the evolution history of
the population, which can be traced back by
re-constructing such given sequences from a
small number of not-yet identified ancestors
(namely founder sequences) using some genetic
operators. Many biological studies have
demonstrated the efficacy of this approach [1].
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 method
for the founder sequence reconstruction
problem. The manuscript is structured
as follows:
• Section 2 first formulates the problem of
founder sequence reconstruction and Section 3
then presents related works that have been
________
* Corresponding author. E-mail.: [email protected]n
59
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
60
successfully applied to the problem with good
results reported.
• Our proposed algorithm, experimental
results and comparisons with previously
proposed state-of-the-art related methods are
described in Section 4.
length
m defined over a finite set S , i.e.,
Ci = Ci1,Ci2 , with Cij S (which can be A,
C, G, T if recombinants of interest are DNA
sequences), we need to find a set of k founder
sequences F = (F , F2 , , each of length
m
1
• Section 5 gives some conclusions for the
proposed method. It also suggests some potential
follow-ups to improve the method further.
defined over the set S . A set F is considered
valid if the set of recombinants C can be
reconstructed from F . This means that, each
recombinant Ci can be decomposed into pi
2. Problem statement
components (1 pi m ) Fr , Fr ,, Fr so
i1
i2
ip
Founder Sequences Reconstruction Problem
(FSRP) is defined as follows:
that each piece Fr ( j =1,2,, pi ) appears at
ij
Given
a
set of
n
recombinants
least once at the same position as in Ci .
C = (C1,C2 ,,Cn ) , each Ci is a sequence of
K
L
Figure 1. Haloptye sequences as recombinants, which are supposed to be originated from a set of 3
predefined founder sequences using a decomposition with 8 breakpoints.
A
valid decomposition is considered
which are part of the founder sequences, is
shown on the right-hand side. Breakpoints are
marked with vertical bars.
The FSRP was first introduced by Ukkonen
[2] and has been proven NP-Hard [6] with
k > 2.
reducible if two consecutive pieces do not
appear in the same founder sequence. Among
such reducible ones the FSRP aims to find out
the optimal decompositions with a minimum
number of required breakpoints. The number of
breakpoints for a solution F can be calculated
n
3. Related work
using the formula:
pi m.
i=1
In this paper we consider a common
biological application in that each recombinant
is a haplotype sequence, i.e. S = {0,1}, where
0 and 1 are the two possible common alleles.
On the left side of Figure 1 is an example of
a set C of 6 haplotype sequences, which is
presented in form of a matrix. In the middle part
This section introduces two state-of-the-art
algorithms proposed for the FSR problem,
namely Recblock [3] and LNS [4], which have
achieved excellent results on benchmark
datasets.
3.1. RecBlock algorithm
RecBlock [3] is a FSR algorithm based on
tree search. Given k founder sequences each of
is a valid founder sequences ( a , b and c )
assuming that the number of founder sequences
is set to 3. The optimal decomposition with 8
breakpoints on the recombinants into sections,
length
m
, the algorithm encodes them as a
matrix with k rows and
m
columns. RecBlock
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
61
reviews the columns of the matrix from left to
right. Vertex Vl at the depth l of the search tree
is part of a solution for the prefix part of the
founders till the column l . Each vertex Vl is
solution found in the current episode is used to
learn (tune ) and go for the next turn.
Our proposed method for FSR has input and
output as follows:
Input: binary matrix C of size n*m
representing a recombinant set and k is the
number of the founder sequences to be found.
Output: binary matrix F of size k *m
string representing the founder sequences so
that BP(C, F) is minimal. Here, BP(C, F) is
labeled with a number of breakpoints BP(Vl ) in
the process of reconstructing recombinants by far.
Recblock uses some strategies to speed up
the reconstruction:
• Only consider the founder sequences in
the alphabet order to avoid revisiting
permutations.
• A vertex is not extended further if its
breakpoint number greater than that of the best
solution so far.
the number of breakpoints required to obtain C
from F .
In general, our ACO based method for FSR
works as depicted in Algorithm 1:
Given two vertices Vl1 and Vl2 at the depth
of
l1
and
l2 ,
respectively,
if
BP(Vl1 ) BP(Vl2 ) n (where
n
is the
number of recombinants), we may ignore Vl1
for downstream analysis.
3.2. Large neighborhood search algorithm
LNS-1c is empirically considered the best
algorithm proposed by far for solving the FSR
problem [4]. This algorithm uses the nearest-
4.2. Structure graph for the FSR problem
neighbor search strategy over
neighborhood of constructed solutions.
a
large
For the sake of visualization, we simulate
the FSR problem as the problem of finding
paths on a corresponding structure graph (see
Figure 2).
During searching the neighborhood, the
algorithm picks out a set Ffree F beforehand,
then uses the algorithm Recblock to search for
This structure graph includes a start, an end
node and
m
columns. Each column has 2k
alternative founder sequences in FFfree
.
Whenever a better solution is found out, LNS-
1c performs local search over neighborhood
from scratch.
vertices, of which each corresponds to a state of
the corresponding column in the matrix F of
founder sequences. In particularly, each state is
a binary string of length k .
4 Proposed method
Each vertex has edges connecting to all
ones in the next column. We can see all paths
starting from the start to the end node has to go
through every column once, at which one state
is chosen. Each journey of ants travelling from
the start to the end node therefore corresponds
to a complete matrix of founder sequences.
4.1. Ant colony optimization based FSR
Ant colony optimization [7] (ACO) is a
metaheuristic method simulating how ants in
nature find paths from their nest to food
sources, which turn out to be a reinforcement
learning method. ACO solves optimization
problems throughout many episodes, in each of
which every ant travels to find solutions based
on heuristic information and pheromone matrix
4.3. How ants travel on the structure graph
When travelling on the structure graph, ants
chose a next vertex to visit at random. The
containing information learned. The best
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
62
algorithm is described in pseudo code in
Algorithm ??. The probability at which a vertex
is chosen is proportional to its level of
compatibility to the matrix constructed by ants
so far. This level is calculated through heuristic
1
a, j
=
BP(Ci , Fa j)
where:
• Ci is the matrix of the first i columns of
matrix C .
• Fa is the solution that ant
(with i 1 columns).
• Fa j is the matrix resulted when ant
intends to visit vertex j .
and pheromone information
the j vertex in the column i will be visited by
an ant with a probability.
. Particularly,
a
has built
[i, j ] [a, j ]
a
P =
i, j
[i,l ] [a,l ]
l
To give an example, when i = 3 we have
the structure graph as in Figure 3.
Where:
•
a, j is the heuristic value (see 4.3.1).
•
i, j is the pheromone information (see
4.3.2).
• , are two parameters of an ACO
determining the correlation between the
heuristic value and the pheromone information.
Figure 3. Structure graph when i = 3.
4.3.2. Pheromone information
In the FSR problem, we denote ij as the
pheromone information of the jth vertex in the
column i in the graph. Vertices being visited in
the optimal solutions found in every searching
phase by ants so far will be learnt such that they
are of high priority to be visited in next phases.
There are various pheromone updating
methods that have been proposed for ACO. We
select the Smoothed Max-Min Ant system [8]
because it yields the best results in our
experiments. In this regard, the pheromone
information is updated after each loop as follows:
4.3.1. Heuristic information
While constructing the optimal solution,
heuristic information is calculated according to
the level of compatibility to the matrix that is
yielded with the next moves of ants. In more
details, when an ant is going to the j vertex in
the column i the heuristic information is
calculated as follows.
ij = (1 )ij ij
where:
if (i, j)T
min
=
ij
maxif (i, j)T
and T is the optimal solution that ants found
after the loop and (i, j) is the vertex j in the
column i of the structure graph.
4.4. Improved ACO for FSRP
4.4.1 Ants find solutions synchronously
Note that the problem solution space is
extremely large, if working independently with
Figure 2. Structure graph for the ACO-based
founder sequence reconstruction.
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
63
each other ants could hardly to concentrate on
potential regions of the searching space. We
therefore propose a search strategy for ants as
follows:
We let ants (in the set Ants) find solutions
in parallel. When moving to the next column,
instead of letting each ant choose the next
vertex to go, we create a new ant set (called
NewAnts) to prolong paths created by ants in
the optimal solution found by far we use RecBlock
to find another alternative better one.
Searching along two dimensions: With the
newly proposed search strategy, ants will
quickly converge onto some solution regions,
leading to a low diversity of found solutions. To
improve this problem, apart from searching
forward from the start to the end vertex, we also
let ants search backward along the opposite
direction (i.e. from the end back to start vertex).
The search direction is periodically changed.
When searching backward, the complete
different heuristic information is used, leading
to the potential of finding new solutions.
the set Ants. In particular, if an ant
the path for an ant , it means that ant a will
go over the similar journey as ant before
a prolongs
a
a
moving to the next vertex in the next column.
When having NewAnts with the same size as
Ants, we move to the next column and repeat
such a new ant set building procedure from
NewAnts until having a complete solution set.
This procedure is depicted in pseudo code in
Algorithm 3.
5. Experimental results
We compare our proposed FSR algorithm
called ACOFSRP with the best corresponding
one by far, i.e. LNS-1c [4] on 3 benchmark data
sets, namely rnd (random), evo and ms (each
contains 6 test set). All sequences in the first
data set is randomly generated while those in
the two latter ones are generated according to
evolutionary models. All three are used in the
study of LNS-1c. We do experiments with the
founder sequence length k 5,6,7,8,9,10 for
For more details, when going from the
column i 1 to the column i , each ant
a NewAnts will randomly choose an ant
a Ants to prolong its path and a vertex j in
the column i to move forward. The ant
a is
chosen with a probability also based on the
heuristic and pheromone information, as
follows:
each of such 3 test sets, leading to a total of
108 tests.
[i, j ] [a, j ]
P =
a, j
[ ] [
]
a ,l
We also do experiments with different
variants of ACOFSRP by not using either one
of two improvements or both on the same three
benchmark sets. Experimental results show that
ACOFSRP outperforms its two variants,
demonstrating the power of two proposed
improvements in ACOFSRP (data not shown).
Due to the random nature of ACOFSRP, we
perform each test 20 times and the run time of
each is limited to 10 hours. These numbers are
1 and 72, respectively, in the study of LNS-1c
[4]. The program is run on a CPU with 12GB
RAM and 4GHz processor. Table ?? shows the
detailed performance, in terms of the solution
quality (number of required breakpoints) and
the running time, of ACOFSRP and LNS-1c on
three benchmark data sets. Note that the values
for ACOFSRP are the averages of those from
20 running times.
i,l
x
a
l
x
4.4.2. Other improvements
Neighborhood search: To lower the
probability of missing good solutions while
searching, we recommend using the reduced
version of the algorithm RecBlock (3.2) to find
other better solutions within the vicinity of the best
by far solution found by ants. Instead of browsing
the whole founder sequences, for each founder in
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
64
Table 1. Detailed performance of our ACOFSRP and LNS-1c on three benchmark sets
# founders
ACOFSRP
Value Time(s) Value Time(s) Value Time(s) Value Time(s) Value Time(s) Value Time(s)
rnd-30_60 evo-30_60 ms-30_60
4520
LNS-1c
ACOFSRP
LNS-1c
ACOFSRP
LNS-1c
5
6
7
8
9
48427
44255
906
3996
145
94
65
45
36
28
372 4501
324 5695
8136
372
324
293
268
145
94
65
45
36
28
4
53
86
353
51
1
124
99
81
69
59
50
124
209
5394
7644
100 98859
5871
7194
17273
54798
2002
289
81
70
60
50
96096
246 175659
12502
27293
36041
263 12361
240 22388
221 34456
11135
17377
33364
10
229
90559
38579
rnd-30_90
evo-30_90
ms-30_90
5
6
7
8
9
72903
79754
55418
07173
12679
6222
8933
10240
114 12369 114
585 6753
585
516
472
426
203
118
69
43
35
203
118
69
43
35
60
52
19
3
69
28
167
136
167
136
747
768
30934
7491
12225
20652
35383
36056
514 8501
461 12506
417 19270
97 126402
85
74
96
83
73
16197
32062
36057
31562 399
382
216
1648
10
370 244167
353 36055
31
31
rnd-30_150
evo-30_150
ms-30_150
5
6
7
8
9
134777
10419
252 11476
976 11244 976
381
230
131
63
39
38
381
230
131
63
39
35
893
72
72
59
1
251
189
4986
1421
25361
7590
106022
22794
865 216875
778 140918
710 250463
666 87405
13178
21422
30531
36071
36120
16279
24401 153
32750
858 14045
766 20532
698 31618
639 36054
591
189
154
125
125
103 36050 103
10
36094 619
36118
ms-50_100
12258
21046
12
88
88
rnd-50_100
1211 9290
1084 12766
985
evo-50_100
5
6
7
8
9
1213 65968
1097 60881
20193 1009
8769
8644
12072
21207
34994 124
36061
36128
368
250
174
123
99
368
250
145
113
310
310
2192
18039
442
251 16089 251
25576 212
174 14706 210
928
44145
875 113792
830 221118
178 51495
910 31773
845 36063
794 36098
149
2507
3696
177 34846
156
138 36137
38758
99
83
36056 155
10
84
137 30080
rnd-50_150
evo-50_150
ms-50_150
18911 429
346 25681 346
5
6
7
8
9
1800 195873
1622 144474
1484 221180
1385 85140
1320 222181
1240 244166
12464
430
48449
26957
1958
1797 14459
1606 19572
1466 31384
1354 36044
1262 36130
1194 36122
522
319
205
135
101
83
522
319
205
135
101
82
132
109
4
169
108
291
19894
33503
36059
36116
36174
287 30661
240 36047
201 36072
175 36120
286
241 130741
203 170493
10
174
8253
rnd-50_250
evo-50_250
ms-50_250
5
6
7
8
9
3043 101246
2725 172785
2508 251951
2330 176486
2204 244380
2097 257557
21491
29774
36042
36072
36186
36269
615 23672
3031 26742
2698 34085
2461 36056
2276 36090
2133 36137
2012 36256
1126
726
450
258
141
85
1126 3060
613
2171
48013
482
726
450
258
1060
259
603
33887 479
36050
396
396 16430
336 23916
338 36076
288
257 36228
243608
7413
141 12100
83 275
36121 283
248
10
A.V.T. Ngoc et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 59-65
65
Acknowledgments
On the random data set ( rnd ), ACOFSRP
could procedure solutions better than LNS-1c
for 32 among total 36 cases. On-par solutions
are observed in the 4 remaining cases.
Regarding the running time, ACOFSRP
requires shorter time than LNS-1c for 32 cases
while longer only for 4 remaining cases.
On the data set evo, ACOFSRP is beated
by LNS-1c in terms of excution time for all
cases. Nevertheless, solutions yielded by
ACOFSRP are on-par with those of LNS-1c for
32 out of 36 cases. For the remaining 4 cases,
the solution goodness scores by ACOFSRP are
worse than those by LNS-1c (The small
This work has been supported by Vietnam
National University, Hanoi (VNU), under
Project No. QG.15.21.
References
[1] G. Tyson, J. Chapman, H. Philip, E. Allen, R.
Ram, P. M. Richardson, V. Solovyev, E. M.
Rubin, D. Rokhsar, J. F. Banfield, Community
structure
and
metabolism
through
reconstruction of microbial genomes from the
environment, Nature 428 (2004) 37–43.
differences are observed, i.e. up to
breakpoints).
3
[2] E. Ukkonen, Finding Founder Sequences from
a
Set of Recombinants, Springer Berlin
Heidelberg,
Berlin,
Heidelberg,
2002,
On the data set ms , ACOFSRP produced
solutions are better than and equal to those
yielded by LNS-1c for 12 and 10 cases,
respectively. Interestingly, among such 22,
ACOFSRP requires remarkably shorter runing
time than LNS-1c for 12 cases. For the
remaining 14 cases, ACOFSRP produce
pp. 277–286.
[3] A. Roli, C. Blum, Tabu Search for the Founder
Sequence Reconstruction Problem:
A
Preliminary Study, Springer Berlin Heidelberg,
Berlin, Heidelberg, 2009, pp. 1035–1042.
[4] A. Roli, S. Benedettini, T. Stützle, C. Blum,
Large neighbourhood search algorithms for the
founder sequence reconstruction problem,
Computers Operations Research 39 (2) (2012)
pp. 213–224.
solutions
worse
than
LNS-
1c. ./table_combine_all.tex
[5] C. Blum, A. Roli, Metaheuristics in
combinatorial optimization: Overview and
conceptual comparison, ACM Comput. Surv.
35 (3) (2003) 268–308.
[6] P. Rastas, E. Ukkonen, Haplotype inference via
hierarchical genotype parsing, in: Proceedings
of the 7th International Conference on
Algorithms in Bioinformatics, WABI’07,
Springer-Verlag, Berlin, Heidelberg, 2007,
pp. 85–97.
6. Conclusion
Founder gene sequence reconstruction
(FSR) for a given population can be modeled as
a combinatorial optimization problem, which
has been proven NP-hard. In this paper we
propose a novel method based on ant colony
optimization algorithms (ACO) coupled with
two other important improvements (i.e. local
search and back forward search) to solve the
founder gene sequence reconstruction problem.
Experiments on the benchmark data sets show
better or equal results for almost sets when
comparing to the best corresponding method,
demonstrating the efficacy and future
perspectives of our proposed method.
[7] M. Dorigo, T. Stützle, Ant Colony
Optimization, Bradford Company, Scituate,
MA, USA, 2004.
[8] D. Do Duc, H. Hoang Xuan, Smooth and three-
levels ant systems: Novel aco algorithms for
solving traveling salesman problem, in: Ad.
Cont. to the International Conference: IEEE-
RIVF 2010, pp. 33–37.
G
g
7 trang
23420
Free
Bạn đang xem tài liệu "Ant colony optimization based founder sequence reconstruction", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- ant_colony_optimization_based_founder_sequence_reconstructio.pdf
