The DNA fragment assembly (DFA) problem is among the most critical problems in computational biology. Being NP-hard, it can be efficiently solved via meta-heuristic algorithms, such as the gravitation search algorithm (GSA). GSA is a state-of-the-art swarm-based algorithm particularly suitable for solving NP-hard combinatorial optimization problems. This paper proposes a new memetic GSA algorithm called MGSA. MGSA is a type of overlap-layout-consensus model that is based on tabu search for population initialization. In order to increase the diversity of MGSA, we adapted two operator time-varying maximum velocities in the GSA procedure. Finally we also adapted the simulated annealing-based variable neighborhood search (SA-VNS) to find superior precise solutions. The proposed MGSA algorithm was verified with 19 DNA fragments based on seeking to maximize the overlap score measurements. In comparing the performances of the proposed MGSA and state-of-the-art algorithms, the simulation results demonstrate that the MGSA can achieve the best overlap scores.
ZhangY., FuB. and ZhangX., Dna cryptography based on DNA fragment assembly, In Information Science and Digital Content Technology (ICIDT), 2012 8th International Conference on, volume 1, 2012, pp. 179–182.
2.
WangR.-Y., ShiZ.-Y., GuoY.-Y., ChenJ.-C. and ChenG.-Q., DNA fragments assembly based on nicking enzyme system, PLoS One8(3) (2013), e57943.
3.
PevznerP.A., Computational molecular biology - an algorithmic approach, MIT Press, 2000.
4.
KatoT. and HasegawaM., Performance of heuristic methods driven by chaotic dynamics for atsp and applications to DNA fragment assembly, Nonlinear Theory and Its Applications, IEICE2(4) (2011), 485–496.
5.
SangerF., CoulsonA.R., HongG.F., HillD.F. and PetersenG.B., Nucleotide sequence of bacteriophage lambda DNA, Journal of Molecular Biology162(4) (1982), 729–773.
6.
HassanienA.E., Al-ShammariE.T. and GhaliN.I., Computational intelligence techniques in bioinformatics, Computational Biology and Chemistry47 (2013), 37–47.
7.
Phil Green, PHRAP, 1994.
8.
BonfieldJ.K., SmithK.F. and StadenR., A new DNA sequence assembly program, Nucleic Acids Res23 (1995), 4992–4999.
9.
SuttonG.G., WhiteO., AdamsM.D. and KerlavageA.R., Tigr assembler: A new tool for asbling large shotgun sequencing projects, Genome Science and Technology1(1) (1995), 9–19.
10.
HuangX. and MadanA., Cap3: A dna sequence assembly program, Genome Research9(9) (1999), 868–877.
11.
ChenT. and SkienaS.S., A case study in genome-level fragment assembly, Bioinformatics16 (2000), 494–500.
12.
MyersE.W., A whole-genome assembly of drosophila, 2000, pp. 2196–2204.
13.
BatzoglouS., JaffeD.B., StanleyK., ButlerJ., GnerreS., MauceliE., BergerB., MesirovJ.P. and LanderE.S., Arachne: A whole-genome shotgun assembler, Genome Res12(1) (2002), 177–189.
14.
GendreauM. and PotvinJ.-Y., Handbook of Metaheuristics, Springer Publishing Company, Incorporated, 2nd edition, 2010.
15.
SchmittK.R.B., ZiminA.V., MarcaçsG., YorkeJ.A. and GirvanM., A hierarchical network heuristic for solving the orientation problem in genome assembly, ArXiv E-Prints (2013).
16.
AlbaE., LuqueG. and KhuriS., Assembling DNA fragments with parallel algorithms. In IEEE Congress on Evolutionary Computation, volume 1, 2005, pp. 57–64.
17.
MinettiG., LeguizamónG. and AlbaE., An improved trajectory-based hybrid metaheuristic applied to the noisy DNA fragment assembly problem, Information Sciences (2014), 273–283.
18.
BaewiczJ., FormanowiczP., MKasprzakW., MarkiewiczT. and WglarzJ., Tabu search for DNA sequencing with false negatives and false positives, European Journal of Operational Research125(2) (2000), 257–265.
19.
WangY., FangS.C. and ZhongJ., A genetic algorithm approach to solving DNA fragment assembly problem, Journal of Computational and Theoretical Nanoscience2 (2005), 499–505.
20.
AlbaE. and LuqueG., A hybrid genetic algorithm for the dna fragment assembly problem. In Recent Advances in Evolutionary Computation for Combinatorial Optimization, 2008, pp. 101–112.
21.
MinettiG., AlbaE. and LuqueG., Seeding strategies and recombination operators for solving the DNA fragment assembly problem, Information Processing Letters108(3) (2008), 94–100.
22.
LuqueG. and AlbaE., Parallel gas in bioinformatics: Assembling DNA fragments, Studies in Computational Intelligence367(9) (2011), 135–147.
23.
HughesJ., HoughtenS., Mallen-FullertonG.M. and AshlockD., Recentering and restarting genetic algorithm variations for dna fragment assembly. In Computational Intelligence in Bioinformatics and Computational Biology, 2014 IEEE Conference on, 2014, pp. 1–8.
24.
HughesJ., A study of ordered gene problems featuring dna error correction and dna fragment assembly with a variety of heuristics, genetic algorithm variations, and dynamic representations, 2014.
25.
RatheeM. and KumarT.V.V., Dna fragment assembly using multi-objective genetic algorithms, International Journal of Applied Evolutionary Computation5(3) (2014), 84–108.
26.
WetcharapornW., ChaiyaratanaN. and TongsimaS., DNA fragment assembly by ant colony and nearest neighbour heuristics, In Proceedings 8th International Conference Artificial Intelligence and Soft Computing, volume 4029, 2006.
27.
IbrahimZ. and KurniawanT.B., Implementation of an ant colony system for DNA sequence optimization, Journal of Artif Life Robotics (2009), 293–296.
28.
BaidyaS. and RajatKumarD., A novel locally guided genome reassembling technique using an artificial ant system, Applied Intelligence43(2) (2015), 397–411.
29.
FirozJ.S., RahmanM.S. and SahaT.K., Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless data. In Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference, 2012, pp. 201–208.
30.
VermaR.S., SinghV. and KumarS., Dna sequence assembly using particle swarm optimization, International Journal of Computer Applications28(10) (2011), 33–38.
31.
FirozJ.S., RahmanM.S. and SahaT.K., Hybrid metaheuristics for DNA fragment assembly problem for noiseless data. In Informatics, Electronics Vision (ICIEV), 2012 International Conference on, 2012, pp. 652–656.
32.
Mallén-FullertonG.M. and Fernandez-AnayaG., DNA fragment asbly using optimization. In Evolutionary Computation (CEC), 2013 IEEE Congress on, 2013, pp. 1570–1577.
33.
HuangK.-W., ChenJ.-L., YangC.-S. and TsaiC.-W., A memetic particle swarm optimization algorithm for solving the dna fragment assembly problem, pp, Neural Computing and Applications, 2014, pp. 1–12.
34.
RajagopalI. and SankareswaranU.M., An adaptive particle swarm optimization algorithm for solving dna fragment assembly problem, Current Bioinformatics10(1) (2015), 97–105.
35.
NazriM.Z.A., HuriM.D., BakarA.A., AbdullahS., DanM.A. and KurniawanT.B., DNA sequence design using artificial immune systems, Journal of Engineering and Applied Sciences8(2) (2013), 49–57.
36.
KartousW. and ChikhiS., Improved cuckoo search algorithm for dna fragment assembly problem, Networking and Advanced Systems, 2015, p. 117.
37.
IndumathyR., MaheswariS. and SubashiniG., Nature-inspired novel cuckoo search algorithm for genome sequence assembly, Sadhana40(1) (2015), 1–14.
38.
VidalP. and OliveraA., A parallel discrete firefly algorithm on gpu for permutation combinatorial optimization problems, 485 (2014), 191–205.
39.
NebroA.J., LuqueG., LunaF. and AlbaE., DNA fragment assembly using a grid-based genetic algorithm, Computers & Operations Research35(9) (2008), 2776–2790.
40.
LuqueG., DorronsoroB., AlbaE. and BouvryP., A self-adaptive cellular memetic algorithm for the DNA fragment assembly problem, In IEEE Congress on Evolutionary Computation, 2008, pp. 2651–2658.
41.
NematiS., BasiriM.E., Ghasem-AghaeeN. and AghdamM.H., A novel acoga hybrid algorithm for feature selection in protein function prediction, Expert Systems with Applications36(10) (2009), 12086–12094.
42.
DorronsoroB., BouvryP. and AlbaE., Iterated local search for de novo genomic sequencing. In RutkowskiLeszek, SchererRafa, TadeusiewiczRyszard, ZadehLot-fiA. and ZuradaJacekM., editors, Artifical Intelligence and Soft Computing, volume 6114 of Lecture Notes in Computer Science, SpringerBerlin Heidelberg, 2010, pp. 428–436.
43.
KubalikJ., BuryanP. and WagnerL., Solving the DNA fragment assembly problem efficiently using iterative optimization with evolved hypermutations. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO’10, 2010, pp. 213–214.
44.
Mallén-FullertonG.M., HughesJ.A., HoughtenS. and Fernández-AnayaG., Benchmark datasets for the dna fragment assembly problem, International Journal of Bio-Inspired Computation5(6) (2013), 384–394.
45.
CompeauP.E.C., PevznerP.A. and TeslerG., How to apply de bruijn graphs to genome assembly, Nature Biotechnology29(11) (2011), 987–991.
46.
MillerJ.R., KorenS. and SuttonG., Assembly algorithms for next-generation sequencing data, Genomics95(6) (2010), 315–327.
47.
LiZ., ChenY., MuD., YuanJ., ShiY., ZhangH., GanJ., LiN., HuX., LiuB., et al., Comparison of the two major classes of assembly algorithms: overlap-layout-consensus and de-bruijn-graph, Briefings in Functional Genomics11(1) (2012), 25–37.
48.
PevznerP.A., TangH. and WatermanM.S., An eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences98(17) (2001), 9748–9753.
49.
SimpsonJ., WongK., JackmanS., ScheinJ., JonesS. and BirolI., Abyss: A parallel assembler for short read sequence data, Genome Res19 (2009), 1117.
50.
GeorganasE., BulucA., ChapmanJ., OlikerL., RokhsarD. and YelickK., Parallel de bruijn graph construction and traversal for de novo genome assembly, In High Performance Computing, Networking, Storage and Analysis, SC14: International Conference for, 2014, pp. 437–448.
51.
CoutoA.D., Ribeiro CerqueiraF., GuerraR.L.,
GoncalvesL.B.,
De Castro GoulartC.,
Siqueira-BatistaR., Dos Santos FerreiraR. and
De Paiva OliveiraA., Theoretical basis of a new method for DNA fragment assembly in k-mer graphs. In Chilean Computer Science Society (SCCC), 2012 31st International Conference of the, 2012, pp. 69–77.
52.
ZhaoK., LiuW., VossG. and Muller-WittigW., A dynamic hashing approach to build the de bruijn graph for genome assembly. In TENCON 2013 - 2013 IEEE Region 10 Conference, 2013, pp. 1–4.
53.
PrjibelskiA.D., VasilinetcI., BankevichA., GurevichA., KrivosheevaT.,
NurkS.,
PhamS.,
KorobeynikovA.,
LapidusA. and
PevznerP.A.,
Exspander: A universal repeat resolver for dna fragment assembly, Bioinformatics30(12) (2014), 293–301.
54.
GritsenkoA.A., NijkampJ.F., ReindersM.J.T. and de RidderD., Grass: A generic algorithm for scaffolding next-generation sequencing assemblies, Bioinformatics28(11) (2012), 1429–1437.
55.
ZiminA.V., MarçaisG., PuiuD., RobertsM., SalzbergS.L. and YorkeJ.A., The masurca genome assembler, Bioinformatics29(21) (2013), 2669–2677.
56.
XuB., GaoJ. and ChunyanL., An efficient algorithm for {DNA} fragment assembly in mapreduce, Biochemical and Biophysical Research Communications426(3) (2012), 395–398.
57.
HassanH., MajidZ.A., HalimA.K. and IbrahimA., Design and development of DNA fragment assembly using iwp method, In Control and System Graduate Research Colloquium (ICSGRC), 2013 IEEE 4th, 2013, pp. 63–68.
58.
WangX.-Z. and DongC.-R., Improving generalization of fuzzy if– then rules by maximizing fuzzy entropy, Fuzzy Systems, IEEE Transactions on17(3) (2009), 556–567.
59.
ZhuZ., ZhouJ., JiZ. and huiS.Y., DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm, IEEE Transactions on Evolutionary Computation15(5) (2011), 643–658.
60.
ZhaiJ.-H., XuH.-Y. and Xi-ZhaoW., Dynamic ensemble extreme learning machine based on sample entropy, Soft {{Computing16(9) (2012), 1493–1502.
61.
RashediE., Nezamabadi-PourH. and SaryazdiS., GSA: A gravitational search algorithm, Information Sciences179(13) (2009), 2232–2248.
62.
KennedyJ. and EberhartR., Particle swarm optimization, In IEEE International Conference on Neural Networks4 (1995), 1942–1948.
63.
Fatih TasgetirenM., LiangY.-C., SevkliM. and GencyilmazG., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research177(3) (2007), 1930–1947.
64.
GloverF. and LagunaM., Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA, 1997.
65.
KirkpatrickS., GelattC.D. and VecchiM.P., Optimization by simulated annealing, Science220 (1983), 671–680.
66.
DawkinsR., The Selfish Gene. Oxford University Press, Oxford, UK, 1976.
67.
MoscatoP., On evolution, search, optimization, genetic algorithms and martial arts - towards memetic algorithms, 1989.
68.
MoscatoP. and CottaC., A gentle introduction to memetic algorithms, 57 (2003), 105–144.
69.
KrasnogorN., AragónA. and PachecoJ., Memetic algorithms, 36 (2006), 225–248.
70.
AlimehrL., The performance of sequence alignment algorithms. Master’s thesis, Uppsala University, Department of Information Technology, 2013.
71.
MetropolisN., RosenbluthA.W., RosenbluthM.N., TellerA.H. and TellerE., Equation of state calculations by fast computing machines, The Journal of Chemical Physics21(6) (1953), 1087–1092.
72.
ParsonsR.J., ForrestS. and BurksC., Genetic algorithms, operators, and DNA fragment assembly, Machine Learning21(1-2) (1995), 11–33.
73.
CoullS.E. and SzymanskiB.K., Sequence alignment for masquerade detection, Computational Statistics & Data Analysis52(8) (2008), 4116–4131.
74.
GaoS., VairappanC., WangY., CaoQ. and TangZ., Gravitational search algorithm combined with chaos for unconstrained numerical optimization, Applied Mathematics and Computation231 (2014), 48–62.
75.
KhajehzadehM., TahaM.R., El-ShafieA. and EslamiM., A modified gravitational search algorithm for slope stability analysis, Engineering Applications of Artificial Intelligence25(8) (2012), 1589–1597.
76.
EngleM.L. and BurksC., Artificially generated data sets for testing DNA sequence assembly algorithms, Genomics16(1) (1993), 286–288.
77.
DerracJ., GarcíaS., MolinaD. and HerreraF., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm and Evolutionary Computation1 (2011), 3–18.
