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 8/2010

01.11.2010 | AIS

An immune-inspired multi-objective approach to the reconstruction of phylogenetic trees

verfasst von: Guilherme P. Coelho, Ana Estela A. da Silva, Fernando J. Von Zuben

Erschienen in: Neural Computing and Applications | Ausgabe 8/2010

Einloggen

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

search-config
loading …

Abstract

This work presents the application of the omni-aiNet algorithm—an immune-inspired algorithm originally developed to solve single and multi-objective optimization problems—to the reconstruction of phylogenetic trees. The main goal here is to automatically evolve a population of phylogenetic unrooted trees, possibly with distinct topologies, by minimizing at the same time two optimization criteria: the minimum evolution and the mean-squared error. This proposal generates, in a single run, a set of non-dominated solutions that represent the trade-offs of the two conflicting objectives, and gives the user the possibility of having distinct explanations for the differences observed at the terminal nodes of the trees. A series of experimental results is also reported in this work, in order to illustrate the effectiveness of the proposal and its capability to overcome the restrictive feedback provided by the application of well-known algorithms for phylogenetic reconstruction, such as the Neighbor Joining. Besides, the methodology presented in this work is compared to the popular NSGA-II algorithm, also modified to solve phylogenetic reconstruction problems.
Vorheriger Artikel Theory and applications of artificial immune systems
Nächster Artikel A graph-based immune-inspired constraint satisfaction search

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
Fußnoten
1
These two criteria were selected in this work because they are two of the most popular ones in the algorithms for phylogenetic reconstruction based on distance matrices. However, the proposed methodology can be easily extended to consider two or more different criteria.
 
Literatur
1.
Smith JM (1993) The theory of evolution. Cambridge University Press, Cambridge
2.
Darwin C (1859) On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life. John Murray, London
3.
Felsenstein J (2004) Inferring phylogenies. Sinauer Associates, Suderland
4.
Kidd KK, Sgaramella-Zonta LA (1971) Phylogenetic analysis: concepts and methods. Am J Hum Genet 23:235–252
5.
Bulmer M (1991) Use of the method of generalized least squares in reconstructing phylogenies from sequence data. Mol Biol Evol 8:868–883
6.
Saitou N, Nei M (1987) The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol Evolution 4(4):406–425
7.
Takahashi K, Nei M (2000) Efficiencies of fast algorithms of phylogenetic inference under the criteria of maximum parsimony, minimum evolution, and maximum likelihood when a large number of sequences are used. Mol. Biol. Evol. 17(8):1251–1258
8.
Eschenauer H, Koski J, Osyczka A (1990) Multicriteria design optimization: procedures and applications. Springer, BerlinMATH
9.
Statnikov RB, Matusov JB (1995) Multicriteria optimization and engineering. Chapman & Hall, New York
10.
Miettinen KM (1999) Nonlinear multiobjective optimization. Kluwer, BostonMATH
11.
Ehrgott M (2005) Multicriteria optimization. Springer, BerlinMATH
12.
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, ChichesterMATH
13.
Coello Coello CA, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, New YorkMATH
14.
Coello Coello CA, Cruz Cortes N (2005) Solving multiobjective optimization problems using an artificial immune system. Genet Program Evol Mach 6:163–190CrossRef
15.
Coelho GP, Von Zuben FJ (2006) omni-aiNet: an immune-inspired approach for omni optimization. In: Proceedings of the fifth international conference on artificial immune systems, Oeiras, Portugal, September 2006, pp 294–308
16.
Coelho GP, da Silva AE, Von Zuben FJ (2007) Evolving phylogenetic trees: a multiobjective approach. In: Proceedings of the Brazilian symposium on bioinformatics. Angra dos Reis, Brazil, August 2007, pp 113–125
17.
Nei M, Kumar S (2000) Molecular evolution and phylogenetics. Oxford University Press, New York
18.
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197CrossRef
19.
Poladian L, Jermiin LS (2004) What might evolutionary algorithms (EA) and multi-objective optimisation (MOO) contribute to phylogenetics and the total evidence debate. In: Proceedings of the genetic and evolutionary computing conference (GECCO 2004). Seattle
20.
Poladian L, Jermiin LS (2006) Multi-objective evolutionary algorithms and phylogenetic inference with multiple data sets. Soft Comput 4(10):359–368CrossRef
21.
Huelsenbeck JP, Crandall KA (1997) Phylogeny estimation and hypothesis testing using maximum likelihood. Annu Rev Ecol Syst 28:437–466CrossRef
22.
Holmes SP (1999) Phylogenies: an overview. Stat Genet 112:81–119
23.
Day WHE (1987) Computational complexity of inferring phylogenies from dissimilarity matrices. Bull Math Biol 49:461–467MATHMathSciNet
24.
25.
Roch S (2006) A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE/ACM Trans Comput Biol Bioinf 3(1):92CrossRefMathSciNet
26.
Sneath PHA, Sokal RR (1973) Numerical taxonomy. Freeman, San FranciscoMATH
27.
Fitch WM, Margoliash E (1967) Construction of phylogenetic trees. Science 155:279–284CrossRef
28.
Saitou N, Imanishi T (1989) Relative efficiencies of the Fitch-Margoliash, maximum-parsimony, maximum-likelihood, minimum-evolution, and neighbor-joining methods of phylogenetic tree construction in obtaining the correct tree. Mol Biol Evol 6(5):514–525
29.
DasGupta B, He X, Jiang T, Li M, Tromp J, Zhang L (1997) On distances between phylogenetic trees. In: Proceedings of the 8th annual ACM—SIAM symposium on discrete algorithms, pp 427–436
30.
Brodal GS, Fagerberger R, Pedersen CNS (2004) Computing the quartet distance between evolutionary trees in time O(n.log(n)). Algorithmica 38:377–395MATHCrossRefMathSciNet
31.
DasGupta B, He X, Jiang T, Li M, Tromp J, Zhang L (2000) On computing the nearest neighbor interchange distance. In: Du D-Z, Pardalos PM, Wang J (eds) Discrete mathematical problems with medical applications, vol 55 of DIMACS series in discrete mathematics and theoretical computer science. Am Math Soc, pp 125–143
32.
Bryant D (2003) A classification of consensus methods for phylogenetics. In: Janowitz MF, Lapoint FJ, Morris FR, Mirkin B, Roberts FS (eds) Bioconsensus, vol 61 of DIMACS series in discrete mathematics and theoretical computer science. Am Math Soc, pp 163–184
33.
34.
Edgeworth FY (1881) Mathematical physics. P. Keagan, London
35.
Pareto V (1896) Cours D’Economie politique. F. Rouge, Lausanne
36.
Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, ReadingMATH
37.
Bäck T, Fogel DB, Michalewicz Z (eds) (2000) Evolutionary computation 1: basic algorithms and operators Institute of Physics Publishing, BristolMATH
38.
Bäck T, Fogel DB, Michalewicz Z (eds) (2000) Evolutionary computation 2: advanced algorithms and operators. Institute of Physics Publishing, BristolMATH
39.
Coello Coello CA (1999) A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowl Inf Syst 1(3):129–156
40.
Coello Coello CA (2006) Evolutionary multi-objective optimization: a historical view of the field. IEEE Comput Intell Mag 1(1):28–36CrossRefMathSciNet
41.
Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef
42.
Corne DW, Knowles JD, Oates MJ (2000) The Pareto envelope-based selection algorithm for multiobjective optimization. In: Proceedings of the parallel problem solving from nature VI conference, pp 839–848
43.
Knowles JD, Corne DW (2000) Approximating the nondominated front using the Pareto archived evolution strategy. Evol Comput 8(2):149–172CrossRef
44.
Coello Coello CA, Toscano Pulido G (2001) Multiobjective optimization using a micro-genetic algorithm. In: Proceedings of the genetic and evolutionary computation conference, (GECCO’2001), San Francisco, pp 274–282
45.
Corne DW, Jerram NR, Knowles JD, Oates MJ (2001) PESA-II: region-based selection in evolutionary multiobjective optimization. In: Proceedings of the genetic and evolutionary computation conference (GECCO-2001), San Francisco, pp 283–290
46.
Zitzler E, Laumanns M, Thiele L (2002) SPEA2: Improving the strength Pareto evolutionary algorithm. In: EUROGEN 2001. Evolutionary methods for design, optimization and control with applications to industrial problems. pp 95–100
47.
de Castro LN, Von Zuben FJ (2005) Recent developments in biologically inspired computing. IGI Publishing, Hershey
48.
de Castro LN, Timmis J (2002) An introduction to artificial immune systems: a new computational intelligence paradigm. Springer, Berlin
49.
Jerne NK (1974) Towards a network theory of the immune system. Annu Immunol Inst Pasteur 125:373–389
50.
Burnet FM (1978) Clonal selection and after. In: Bell GI, Perelson AS, Pimgley GH Jr. (eds) Theoretical immunology. Marcel Dekker Inc, New York, pp 63–85
51.
Sareni B, Krähenbühl L (1998) Fitness sharing and niching methods revisited. IEEE Trans Evol Comput 2(3):97–106CrossRef
52.
Freschi F, Repetto M (2005) Multiobjective optimization by a modified artificial immune system algorithm. In: Proceedings of the 4th international conference on artificial immune systems (ICARIS), Banff, pp 248–261
53.
Jiao L, Gong M, Shang R, Du H, Lu B (2005) Clonal selection with immune dominance and anergy based multiobjective optimization. In: Proceedings of the 3rd international conference on evolutionary multi-criterion optimization (EMO), Guanajuato, pp 474–489
54.
Lu B, Jiao L, Du H, Gong M (2005) IFMOA: Immune forgetting multiobjective optimization algorithm. In: Proceedings of the 1st international conference on natural computation (ICNC), Changsha, pp 399–408
55.
Shang R, Ma W (2006) Immune clonal MO algorithm for ZDT problems. In: Proceedings of the 2nd international conference on natural computation (ICNC), Xi’an, pp 100–109
56.
Castro PAD, Von Zuben FJ (2008) MOBAIS: A bayesian artificial immune system for multi-objective optimization. In: Bentley P, Lee D, Jung S (eds) Proceedings of the 7th international conference on artificial immune system vol. 5132 of lecture notes in computer science, Phuket, pp 48–59
57.
Deb K, Tiwari S (2005) Omni-optimizer: a procedure for single and multi-objective optimization. In: Proceedings of the 3rd international conference on evolutionary multi-criterion optimization (EMO), Guanajuato, pp 47–61
58.
de Castro LN, Von Zuben FJ (2001) aiNet: an artificial immune network for data analysis. In: Abbass HA, Sarker RA, Newton CS (eds) Data mining: a heuristic approach. Idea Group Publishing, pp 231–259
59.
de Castro LN, Timmis J (2002) An artificial immune network for multimodal function optimization. In: Proceedings of the IEEE conference on evolutionary computation (CEC), Honolulu, pp 699–704
60.
de Castro LN, Von Zuben FJ (2002) Learning and optimization using the clonal selection principle. IEEE Trans Evol Comput 6(3):239–251CrossRef
61.
Gomes LCT, de Sousa JS, Bezerra GB, de Castro LN, Von Zuben FJ (2003) Copt-ainet and the gene ordering problem. Inf Technol Mag, Cathol Univ Brasília 3(2):27–33
62.
de França FO, Von Zuben FJ, de Castro LN (2005) An artificial immune network for multimodal function optimization on dynamic environments. In: Proceedings of the genetic and evolutionary computation conference (GECCO), Washington, pp 289–296
63.
Castro PAD, de França FO, Ferreira HM, Von Zuben FJ (2007) Applying biclustering to text mining: an immune-inspired approach. In: Proceedings of the 6th international conference on artificial immune systems (ICARIS), Santos, pp 83–94
64.
Rudolph G, Agapie A (2000) Convergence properties of some multi-objective evolutionary algorithms. In: Proceedings of the IEEE conference on evolutionary computation (CEC), Piscataway, pp 1010–1016
65.
Ohno S (1970) Evolution by gene duplication. Allen and Unwin, London
66.
Holland PWH, Garcia-Fernandez J, Williams NA, Sidow A (1994) Gene duplications and the origins of vertebrate development. Development (Suppl):125–133
67.
68.
69.
Tamura K, Dudley J, Nei M, Kumar S (2007) MEGA4: molecular evolutionary genetics analysis (MEGA) software version 4.0. Mol Biol Evol 24:1596–1599CrossRef
70.
Bartélemy JP, Guénoche A (1991) Trees and proximity representations. Wiley, Chichester
71.
Faiger H, Ivanchenko M, Haran TE (2007) Nearest-neighbor non-additivity versus long-range non-additivity in TATA-box structure and its implications for TBP-binding mechanism. Nucleic Acids Res 35(13):4409–4419
72.
Carleton MD (1988) Systematics and evolution. In: Kirkland GL Jr, Layne JN (eds) Advances in the study of Peromyscus (Rodentia). Texas Tech University Press, TX, pp 7–140
73.
Bermingham E, Moritz C (1998) Comparative phylogeography: concepts and applications. Mol Ecol 7:367–369CrossRef
74.
MacLeod N, Forey PL (eds) (2002) Morphology, shape and phylogeny. Systematics association special volume. Taylor & Francis, UK
75.
da Silva AEA, Villanueva WJP, Knidel H, Bonato V, dos Reis SF, Von Zuben FJ (2005) A multi-neighbor-joining approach for phylogenetic tree reconstruction and visualization. Genet Mol Res 4(3):525–534
76.
Bonato V (2004) Patterns of geographic variation in Thrichomys apereoides (Rodentia: Echimyidae). PhD thesis (in Portuguese), Department of Ecology, University of Campinas, Campinas
77.
Zitzler E (1999) Evolutionary Algorithms for Multiobjective Optimization. PhD thesis, Swiss Federal Institute of Technology, Zürich
Metadaten
Titel
An immune-inspired multi-objective approach to the reconstruction of phylogenetic trees
verfasst von
Guilherme P. Coelho
Ana Estela A. da Silva
Fernando J. Von Zuben
Publikationsdatum
01.11.2010
Verlag
Springer-Verlag
Erschienen in
Neural Computing and Applications / Ausgabe 8/2010
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-010-0389-1

Weitere Artikel der Ausgabe 8/2010

Neural Computing and Applications 8/2010 Zur Ausgabe

Original Article

Real-time removal of ocular artifacts from EEG based on independent component analysis and manifold learning

AIS

A graph-based immune-inspired constraint satisfaction search

Original Article

Analysis of international debt problem using artificial neural networks and statistical methods

Original Article

Pose invariant face recognition based on hybrid-global linear regression

Original Article

Self-tuning output recurrent cerebellar model articulation controller for a wheeled inverted pendulum control

Original Article

Genetic algorithm–based training for semi-supervised SVM

Premium Partner

    Bildnachweise