Analysis of a genetic programming algorithm for association studies
Pages 1259 - 1266
Abstract
In this paper a Genetic Programming algorithm for genetic association studies is reconsidered. It is shown, that the application field of the algorithm is not restricted to genetic association studies, but that the algorithm can also be applied to logic minimization problems. In the context of multi-valued logic minimization on incompletely specified truth tables it outperforms existing algorithms. In addition, the facilities of the algorithm in the original application field are complemented by new results and experiments. This includes answers to the open questions of how to automatically choose the best individual in the last population and whether crossover is necessary for the algorithm.
References
[1]
W. Banzhaf, F. D. Francone, R. E. Keller, and P. Nordin. Genetic programming: an introduction: on the automatic evolution of computer programs and its applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998.
[2]
R. K. Brayton, A. L. Sangiovanni-Vincentelli, C. T. McMullen, and G. D. Hachtel. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Norwell, MA, USA, 1984.
[3]
L. Breiman. Bagging predictors. Mach. Learn., 26:123--140, 1996.
[4]
L. Breiman. Random Forests. Mach. Learn., 45:5--32, 2001.
[5]
L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and regression trees. Wadsworth, Belmont, CA, 1984.
[6]
W. J. Conover. Practical Nonparametric Statistics. John Wiley and Sons, third edition, 1999.
[7]
M. de Berg, M. van Krefeld, M. Overmars, and O. Schwarzkopf. Computational Geometry - Algorithms and Applications. Springer, 1997.
[8]
S. Droste. Efficient genetic programming for finding good generalizing Boolean functions. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzo, H. Iba, and R. L. Riolo, editors, Proceedings of the Second Annual Conference on Genetic Programming, pages 82--87, San Francisco CA, 1997. Morgan Kaufmann Publishers, Inc.
[9]
J. Dussault, G. Metze, and M. Krieger. A multivalued switching algebra with boolean properties. In Proceedings of the sixth international symposium on Multiple-valued logic, pages 68--73, Los Alamitos, CA, USA, 1976. IEEE Computer Society Press.
[10]
G. A. Heidema, J. M. A. Boer, N. Nagelkerke, E. C. M. Mariman, D. L. van der A, and E. J. M. Feskens. The challenge for genetic epidemiologists: How to analyze large numbers of SNPs in relation to complex diseases. BioMed Genet., 7(23), 2006.
[11]
J. Hoh and J. Ott. Mathematical multi-locus approaches to localizing complex human trait genes. Nat. Rev. Genet., 4:701--709, 2003.
[12]
M. Hollander and D. A. Wolfe. Nonparametric Statistical Methods. John Wiley and Sons, second edition, 1999.
[13]
J. R. Koza. Genetic Programming. The MIT Press, Cambridge. Massachusetts, 1992.
[14]
J. R. Koza. Genetic Programming II. The MIT Press, Cambridge. Massachusetts, 1994.
[15]
J. T. Kristensen and P. B. Miltersen. Finding small obdds for incompletely specified truth tables is hard. In Proceedings of COCOON 2006, volume 4112 of Lecture Notes in Computer Science, pages 489--496. Springer, 2006.
[16]
R. Nunkesser. RFreak: R/FrEAK interface, 2007. R package version 0.2-0.
[17]
R. Nunkesser, T. Bernholt, H. Schwender, K. Ickstadt, and I. Wegener. Detecting high-order interactions of single nucleotide polymorphisms using genetic programming. Bioinformatics, 23(24):3280--3288, 2007.
[18]
R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2007.
[19]
I. Ruczinski, C. Kooperberg, and M. LeBlanc. Logic regression. J. Comput. Graph. Stat., 12:475--511, 2003.
[20]
R. L. Rudell and A. Sangiovanni-Vincentelli. Multiple-valued minimization for pla optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5):727--750, 1987.
[21]
T. Sasao. Multiple-valued decomposition of generalized boolean functions and the complexity of programmable logic arrays. IEEE Trans. Comput., 30(9):635--643, 1981.
[22]
H. Schwender and A. Fritsch. scrime: Analysis of High-Dimensional Categorical Data such as SNP Data, 2008. R package version 1.0.0.
[23]
S. Y. H. Su and A. A. Sarris. The relationship between multivalued switching algebra and boolean algebra under different definitions of complement. IEEE Trans. Comput., 21(5):479--485, 1972.
[24]
R. Tibshirani, G. Walther, and T. Hastie. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2):411--423, 2001.
[25]
E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evolutionary Computation, 3(4):257--271, 1999.
Index Terms
- Analysis of a genetic programming algorithm for association studies
Recommendations
Neural network crossover in genetic algorithms using genetic programming
AbstractThe use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...
Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover
Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we ...
Evolving dynamic fitness measures for genetic programming
Highlights- Further research is conducted on dynamic fitness measure genetic programming.
- ...
AbstractThis research builds on the hypothesis that the use of different fitness measures on the different generations of genetic programming (GP) is more effective than the convention of applying the same fitness measure individually ...
Comments
Information & Contributors
Information
Published In
July 2008
1814 pages
Copyright © 2008 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2008
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 155Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in