Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Neural Computing and Applications
Erschienen in: Neural Computing and Applications 3/2015

01.04.2015 | Advances in Intelligent Data Processing and Analysis

A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem

verfasst von: Ko-Wei Huang, Jui-Le Chen, Chu-Sing Yang, Chun-Wei Tsai

Erschienen in: Neural Computing and Applications | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Determining the sequence of a long DNA chain first requires dividing it into subset fragments. The DNA fragment assembly (DFA) approach is then used for reassembling the fragments as an NP-hard problem that is the focus of increasing attention from combinatorial optimization researchers within the computational biology community. Particle swarm optimization (PSO) is one of the most important swarm intelligence meta-heuristic optimization techniques to solve NP-hard combinatorial optimization problems. This paper proposes a memetic PSO algorithm based on two initialization operators and the local search operator for solving the DFA problem by following the overlap–layout–consensus model to maximize the overlapping score measurement. The results, based on 19 coverage DNA fragment datasets, indicate that the PSO algorithm combining tabu search and simulated annealing-based variable neighborhood search local search can achieve the best overlap scores.
Vorheriger Artikel Special issue: advances in intelligent data processing and analysis (part II)
Nächster Artikel Hybrid evolutionary algorithms for classification data mining

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Wang R-Y, Shi Z-Y, Guo Y-Y, Chen J-C, Chen G-Q (2013) DNA fragments assembly based on nicking enzyme system. PLoS One 8(3):e57943
2.
Zhang Y, Fu B, Zhang X (2012) Dna cryptography based on DNA fragment assembly. In: Information science and digital content technology (ICIDT), 2012 8th international conference on, vol 1, pp 179–182
3.
Staden R (1980) A new computer method for the storage and manipulation of DNA gel reading data. Nucleic Acids Res 8(16):3673–3694CrossRef
4.
Sanger F, Coulson AR, Hong GF, Hill DF, Petersen GB (1982) Nucleotide sequence of bacteriophage lambda DNA. J Mol Biol 162(4):729–73CrossRef
5.
Hassanien AE, Al-Shammari ET, Ghali NI (2013) Computational intelligence techniques in bioinformatics. Comput Biol Chem 47:37–47CrossRef
6.
Sutton GG, White O, Adams MD, Kerlavage AR (1995) Tigr assembler: a new tool for assembling large shotgun sequencing projects. Genome Sci Technol 1(1):9–19CrossRef
7.
8.
Huang X, Madan A (1999) Cap3: a DNA sequence assembly program. Genome Res 9(9):868–877CrossRef
9.
Chen T, Skiena SS (2000) A case study in genome-level fragment assembly. Bioinformatics 16:494–500CrossRef
10.
Bonfield JK, Smith KF, Staden R (1995) A new DNA sequence assembly program. Nucleic Acids Res 23:4992–4999CrossRef
11.
Myers EW (2000) A whole-genome assembly of drosophila, pp 2196–2204
12.
Batzoglou S, Jaffe DB, Stanley K, Butler J, Gnerre S, Mauceli E, Berger B, Mesirov JP, Lander ES (2002) Arachne: a whole-genome shotgun assembler. Genome Res 12(1):177–189CrossRef
13.
Bocicor M, Czibula G, Czibula I (2011) A reinforcement learning approach for solving the fragment assembly problem. In: Symbolic and numeric algorithms for scientific computing (SYNASC), 2011 13th international symposium on, pp 191–198
14.
15.
Caserta M, Vo S (2014) A hybrid algorithm for the DNA sequencing problem. Discrete Appl Math 163 Part 1(0):87–99
16.
Pevzner PA (2000) Computational molecular biology—an algorithmic approach. MIT Press, Cambridge, MAMATH
17.
Schmitt KRB, Zimin AV, Marcaçs G, Yorke JA, Girvan M (2013) A hierarchical network heuristic for solving the orientation problem in genome assembly. ArXiv e-prints
18.
Burks C, Engle M, Forrest S, Parsons R, Soderlund C, Stolorz P (1994) Stochastic optimization tools for genomic sequence assembly. Automated DNA sequencing and analysis. Academic Press, London
19.
Alba E, Luque G, Khuri S (2005) Assembling DNA fragments with parallel algorithms. In: IEEE congress on evolutionary computation, vol 1, pp 57–64
20.
Baewicz J, Formanowicz P, Kasprzak M, Markiewicz WT, Wglarz J (2000) Tabu search for DNA sequencing with false negatives and false positives. Euro J Oper Res 125(2):257–265CrossRef
21.
Parsons RJ, Forrest S, Burks C (1995) Genetic algorithms, operators, and DNA fragment assembly. Mach Learn 21(1–2):11–33
22.
Fang SC, Wang Y, Zhong J (2005) A genetic algorithm approach to solving DNA fragment assembly problem. J Comput Theor Nanosci 2:499–505CrossRef
23.
Kikuchi S, Chakraborty G (2006) Heuristically tuned GA to solve genome fragment assembly problem. In: IEEE congress on evolutionary computation, pp 1491–1498
24.
Alba E, Luque G (2008) A hybrid genetic algorithm for the dna fragment assembly problem. In: Recent advances in evolutionary computation for combinatorial optimization, pp 101–112
25.
Minetti G, Alba E, Luque G (2008) Seeding strategies and recombination operators for solving the DNA fragment assembly problem. Inf Process Lett 108(3):94–100CrossRefMathSciNet
26.
Luque G, Alba E (2011) Parallel gas in bioinformatics: assembling DNA fragments. Stud Comput Intell 367(9):135–147CrossRefMathSciNet
27.
Meksangsouy P, Chaiyaratana N (2003) DNA fragment assembly using an ant colony system algorithm. In: The congress on evolutionary computation, vol 3, 1756–1763
28.
Wetcharaporn W, Chaiyaratana N, Tongsima S (2006) DNA fragment assembly by ant colony and nearest neighbour heuristics. In: Proceedings 8th international conference artificial intelligence and soft computing, vol 4029
29.
Ibrahim Z, Kurniawan TB (2009) Implementation of an ant colony system for DNA sequence optimization. J Artif Life Robot 293–296
30.
Firoz JS, Rahman MS, Saha TK (2012) 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, pp 201–208
31.
Nazri MZA, Huri MD, Bakar AA, Abdullah S, Dan AM, Kurniawan TB (2013) DNA sequence design using artificial immune systems. J Eng Appl Sci 8(2):49–57
32.
Dorronsoro B, Bouvry P, Alba E (2010) Iterated local search for de novo genomic sequencing. In: Rutkowski L, Scherer R, Tadeusiewicz R, Zadeh L, Zurada JM (eds) Artificial intelligence and soft computing, volume 6114 of lecture notes in computer science. Springer, Berlin, pp 428–436
33.
Kubalik J, Buryan P, Wagner L (2010) 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, pp 213–214
34.
Kato T, Hasegawa M (2011) Performance of heuristic methods driven by chaotic dynamics for ATSP and applications to DNA fragment assembly. Nonlinear Theory Appl IEICE 2(4):485–496CrossRef
35.
Luque G, Dorronsoro B, Alba E, Bouvry P (2008) A self-adaptive cellular memetic algorithm for the DNA fragment assembly problem. In: IEEE congress on evolutionary computation, pp 2651–2658
36.
Minetti G, Luque G, Alba E (2008) Variable neighborhood search as genetic algorithm operator for DNA fragment assembling problem. In: Eighth international conference on hybrid intelligent systems, pp 714–719
37.
Nemati S, Basiri ME, Ghasem-Aghaee N, Aghdam MH (2009) A novel acoga hybrid algorithm for feature selection in protein function prediction. Expert Syst Appl 36(10):12086–12094CrossRef
38.
Minetti G, Leguizamon G, Alba E (2012) Sax: a new and efficient assembler for solving DNA fragment assembly problem. In: 13th Argentine symposium on artificial intelligence
39.
Minetti G, Leguizamn G, Alba E (2014) An improved trajectory-based hybrid metaheuristic applied to the noisy DNA fragment assembly problem. Inf Sci 277:273–283
40.
Nebro AJ, Luque G, Luna F, Alba E (2008) DNA fragment assembly using a grid-based genetic algorithm. Comput Oper Res 35(9):2776–2790CrossRefMATH
41.
Verma RS, Singh V, Kumar S (2011) Article: DNA sequence assembly using particle swarm optimization. Int J Comput Appl 28(10):33–38
42.
Huang K-W, Chen J-L, Yang C-S (2012) A hybrid PSO-based algorithm for solving DNA fragment assembly problem. In: Third international conference on innovations in bio-inspired computing and applications, pp 223–228
43.
Firoz JS, Rahman MS, Saha TK (2012) Hybrid meta-heuristics for DNA fragment assembly problem for noiseless data. In: Informatics, electronics vision (ICIEV), 2012 international conference on, pp 652–656
44.
Mallen-Fullerton GM, Fernandez-Anaya G (2013) DNA fragment assembly using optimization. In: Evolutionary computation (CEC), 2013 IEEE congress on, pp 1570–1577
45.
Compeau PEC, Pevzner PA, Tesler G (2011) How to apply de bruijn graphs to genome assembly. Nat Biotechnol 29(11):987–991CrossRef
46.
Miller JR, Koren S, Sutton G (2010) Assembly algorithms for next-generation sequencing data. Genomics 95(6):315–327CrossRef
47.
Li Z, Chen Y, Mu D, Yuan J, Shi Y, Zhang H, Gan J, Li N, Xuesong H, Liu B et al (2012) Comparison of the two major classes of assembly algorithms: overlap–layout–consensus and de-bruijn-graph. Brief Funct Genomics 11(1):25–37CrossRef
48.
Pevzner PA, Tang H, Waterman MS (2001) An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci 98(17):9748–53CrossRefMATHMathSciNet
49.
Simpson J, Wong K, Jackman S, Schein J, Jones S, Birol I (2009) Abyss: a parallel assembler for short read sequence data. Genome Res 19:1117CrossRef
50.
Xu B, Gao J, Li C (2012) An efficient algorithm for DNA fragment assembly in mapreduce. Biochem Biophys Res Commun 426(3):395–398CrossRef
51.
Couto AD, Cerqueira FR, Guerra RL, Goncalves LB, Goulart CDC, Siqueira-Batista R, Ferreira RDS, Oliveira ADP (2012) 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, pp 69–77
52.
Gritsenko AA, Nijkamp JF, Reinders MJT, de Ridder D (2012) Grass: a generic algorithm for scaffolding next-generation sequencing assemblies. Bioinformatics 28(11):1429–1437CrossRef
53.
Hassan H, Majid ZA, Halim AK, Ibrahim A (2013) Design and development of DNA fragment assembly using IWP method. In: Control and system graduate research colloquium (ICSGRC), 2013 IEEE 4th, pp 63–68
54.
55.
56.
57.
Swarnkar R, Tiwari MK (2004) Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach. Robot Comput Integr Manuf 20(3):199–209CrossRef
58.
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092CrossRef
59.
Bandyopadhyay S, Saha S, Maulik U, Deb K (2008) A simulated annealing-based multiobjective optimization algorithm: AMOSA. IEEE Trans Evol Comput 12(3):269–283CrossRef
60.
Liu B, Wang L, Jin Y-H (2007) An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Trans Syst Man Cybern Part B Cybern 37(1):18–27CrossRef
61.
Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177(3):1930–1947CrossRefMATH
62.
Gendreau M, Potvin J-Y (2010) Handbook of metaheuristics, 2nd edn. Springer Publishing Company, Berlin 
63.
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE international conference on neural networks, vol 4, pp 1942–1948
64.
Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: IEEE international conference on systems, man, and cybernetics, vol 5, pp 4104–4108
65.
Shi Y, Eberhart R (1998) A modified particle swarm optimizer. In: Proceedings of IEEE international conference on evolutionary computation, pp 69–73
66.
67.
Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6(2):154–160CrossRefMATH
68.
Onwubolu GC, Davendra D (2009) Differential evolution: a handbook for global permutation-based combinatorial optimization. Springer Publishing Company, Berlin 
69.
Engle ML, Burks C (1993) Artificially generated data sets for testing DNA sequence assembly algorithms. Genomics 16(1):286–288CrossRef
70.
Yang C-S, Chuang L-Y, Ke C-H, Yang C-S (2008) Comparative particle swarm optimization (CPSO) for solving optimization problems. In: Research, innovation and vision for the future, 2008. RIVF 2008. IEEE international conference on, pp 86–90
71.
Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inf Sci 179(13):2232–2248CrossRefMATH
72.
Derrac J, Garca S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1:3–18CrossRef
73.
Zhu Z, Zhou J, Ji Z, Shi Y (2011) DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm. IEEE Trans Evol Comput 15(5):643–658CrossRef
74.
Zhan Z-H, Zhang J, Li Y, Shi Y (2011) Orthogonal learning particle swarm optimization. IEEE Trans Evol Comput 15(6):832–847CrossRef
75.
Senthilnath J, Omkar SN, Mani V (2011) Clustering using firefly algorithm: performance study. Swarm Evol Comput 1(3):164–171CrossRef
Metadaten
Titel
A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem
verfasst von
Ko-Wei Huang
Jui-Le Chen
Chu-Sing Yang
Chun-Wei Tsai
Publikationsdatum
01.04.2015
Verlag
Springer London
Erschienen in
Neural Computing and Applications / Ausgabe 3/2015
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-014-1659-0

Weitere Artikel der Ausgabe 3/2015

Neural Computing and Applications 3/2015 Zur Ausgabe

Review

Applying the ensemble artificial neural network-based hybrid data-driven model to daily total load forecasting

Original Article

Solving time-varying quadratic programs based on finite-time Zhang neural networks and their application to robot tracking

Original Article

Black box modeling of PIDs implemented in PLCs without structural information: a support vector regression approach

Original Article

A study of visual behavior of multidimensional scaling for kernel perceptron algorithm

Advances in Intelligent Data Processing and Analysis

Stable fuzzy logic control of a general class of chaotic systems

Original Article

How important is a transfer function in discrete heuristic algorithms