James A. Foster

Microbial diversity (metagenomics, microbial ecology and diversity, bioinformatics)

We are developing techniques and tools with which to infer the makeup of a microbial community from the DNA present in a sample, without our having to sequence the DNA or culture the microbes. We are particularly interested in microbial communities in the human microbiome. We are beginning to perform wetbench experiements in addition to our in silico and mathematical projects. Our goal is to understand why different ecosystems host the communities they do, and how those communities change in response to evolutionary dynamics. See our Microbial Community Analysis (MiCA) website.

Evolutionary computation and algorithmics (bioinformatics, computational biology)

We are applying evolutionary computation to address problems in bioinformatics. For example, we have deveoped and tested algorithms that use genetic programming and genetic algorithms for multiple (DNA or protein) sequence alignment, and for phylogenetic reconstruction. Algorithms are springboards for two directions of development: tools for practicioners, especially those with large volumes of data; and theoretical limits to algorithmic efficiency for these problems.

Simulation of molecular evolution (computational biology)

We have developed sophisticated computer simulations . One system simulates the evolution of DNA sequences which undergo reverse transcription. This simulator maintains complete sequence information and can be configured to accommodate a wide range of assumptions about the mechanisms and parameters involved. Our intended model system was mammalian retrotransposons, but the system is not tied to any particular biological system. The objective is to understand the dynamics of evolving systems with multiple levels of selection.

Limitations to evolutionary computing

We have been investigating the phenomenon of code growth in genetic programming, from both a theoretical and an empirical point of view.

We have also investigated the effect of different pseudorandom number generators on the performance of genetic algorithms.

We are also exploring computational complexity and evolutionary computation.

• Ahrens, B. (2005). Genetic algorithm optimization of superresolution parameters. In H.-G. Beyer, U.-M. O'Reilly, D. V. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantú-Paz, D. Dasgupta, K. Deb, J. A. Foster, E. D. de Jong, H. Lipson, X. Llora, S. Mancoridis, M. Pelikan, G. R. Raidl, T. Soule, A. M. Tyrrell, J.-P. Watson, & E. Zitzler (Eds.), 2 (pp. 2083-89). Washington DC: ACM Press. view document.
• Banzhaf, W., Beslon, G., Christensen, S., Foster, J. A., Képès, F., Lefort, V. et al. (2006). From artificial evolution to computational evolution: a manifesto view document.
• Banzhaf, W., Beslon, G., Christensen, S., Foster, J. A., Képès, F., Lefort, V. et al. (2006). From artificial evolution to computational evolution: a research agenda. Nature Reviews. Genetics, 7, 729-35. view document.
• Brown, C. J., Johnson, A. K., Foster, J. A., & Forney, L. J. (2005). High throughput analysis of gene sequences from microbial communities view document.
• Clough, J. E., Foster, J. A., Barnett, M., & Wichman, H. A. (1996). Computer simulation of transposable element evolution: random template and strict master models. Journal of Molecular Evolution, 42(1)(1), 52-58. view document.
• Danielson, W. F., Foster, J. A., & Frincke, D. (1998). GABSyS: Using genetic algorithms to breed a combustion engine. (Eds.), (pp. 259-64). IEEE Press. view document.
• Determan, J. C., & Foster, J. A. (1999). Using chaos in genetic algorithms. (Eds.), (pp. 2094-101). IEEE press. view document.
• Determan, J. C., & Foster, J. A. (2001). A genetic algorithm for expert system rule generation [International conference on genetic and evolutionary computation]. Morgan Kaufmann. view document.
• Determan, J. C., & Foster, J. A. (2001). A genetic algorithm for expert system rule generation view document.
• Determan, J. C., & Foster, J. A. (2002). Fault tolerance in evolved sorting networks: the mechanism responsible for inherent robustness view document.
• Dumoulin, J., McGrew, S., Frenzel, J., & Foster, J. A. (2000). Special Purpose image convolution with evolvable hardware. In S. cagnoni (Ed.), LNCS 1803 (pp. 1-11).
• Evans, J., & Foster, J. A. (2003). Tabu Search: A fast heuristic search algorithm for large data sets [Biology 545 poster session]. Moscow:
• Evans, J., & J. A. Foster. (2003). Searching phylogenetic tree space efficiently Moscow:
• Evans, J., & Foster, J. A. (2004). Speeding up parsimony scoring with streaming SIMD extensions 2 view document.
• Evans, J., Sheneman, L., & Foster, J. A. (2006). Relaxed neighbor joining: a fast distance-based phylogenetic tree construction method. Journal of Molecular Evolution, 62(6)(6), 785-92. view document.
• Forney, L. J., & Foster, J. A. (2008). Advances in the use of terminal restriction fragment length polymorphism (T-RFLP) analysis of 16S rRNA genes to characterize microbial communities [Applied Microbiology and Biotechnology]. view document.
• Forney, L. J., & Foster, J. A. (2010). characterization of vaginal microflora view document.
• Forney, L. J., Foster, J. A., & Ledger, W. (2006). The vaginal flora of healthy women is not always dominated by Lactobacillus sp. Journal of Infectious Disease, 194, 1468-69. view document.
• Foster, J. A. (1993). The generic oracle hypothesis is false. Information Processing Letters, 45, 59-62. view document.
• Foster, J. A. (1995). Exploring the polynomial hierarchy with generic sets. Journal of computing and information, 166-83. view document.
• Foster, J. A., Barnett, M., Van Houten, K., & Sheneman, L. (1995). (In-)Formal methods: teaching program derivation via the Moore method. Computer Science Education, 6(1)(1), 67-91. view document.
• Foster, J. A., Oman, P. W., & Van Houten, K. (1993). Representing arbitrary trees as self-delimiteng binary strings. Congressus Numerantium, 96, 47-56. view document.
• Foster, J. A., Oman, P. W., Van Houten, K., & Zhu, W. (1995). Using Self-delimiting strings to represent trees. Congressus Numerantium, 107, 5-22. view document.
• Foster, J. A. (2001). Evolutionary computation. Nature Reviews. Genetics, 2, 428-36.
• Foster, J. A. (2001). Digital genetics: evolution in your computer view document.
• Foster, J. A., Krone, S. M., & Forney, L. J. (2009). Application of Ecological Network Theory to the Human Microbiome. Interdisciplinary perspectives on infectious disease, 6 pp. view document.
• Goh, G. K.-M., & Foster, J. A. (2000). Evolving Molecules for Drug Design Using Genetic Algorithms via Molecular Trees. (Eds.), (pp. 27-33). view document.
• Goh, G. K.-M., & Foster, J. A. (2000). evolving molecules for drug design using genetic algorithms [congress on evolutionary computation]. view document.
• Goh, G. K.-M., Romero, P., Brown, C. J., Foster, J. A., Uversky, V. N., & Dunker, A. K. (2006). PONDRing Signaling Domains view document.
• Goh, G. K.-M., Brown, C. J., Foster, J. A., & Dunker, A. K. (2006). Effects of Heteroatom and Biopolymer Ligands on Protein Disorder and Disorder Prediction view document.
• Goh, G. K.-M., Romero, P., Brown, C. J., Foster, J. A., Uversky, V. N., & Dunker, A. K. (2006). A PONDR Database of Heteroatom and Polynucleotide Binding Sites: Applications and Analyses
• Goh, G. K.-M., Romero, P., Brown, C. J., Foster, J. A., Uversky, V. N., & Dunker, A. K. (2006). Effects of Ligand Binding and Prediction Discreteness on Protein Disorder Prediction view document.
• Goh, G. K.-M., Romero, P., Brown, C. J., Foster, J. A., Uversky, V. N., & Dunker, A. K. (2006). Effects of the Presence of Polynucleotide Binding Sites on Protein Disorder Prediction view document.
• Harrison, M. (2004). Using co-evolution to improve the fault toleraqnce of sorting networks (Doctoral dissertation, University of Idaho, 2004). view document.
• Harrison, M., & Foster, J. A. (2004). Co-evolving faults to improve the fault tolerance of sorting networks. Genetic Programming, LNCS 3003, 57-66. view document.
• Harrison, M. L., & Foster, J. A. (2004). Improving the survivability of a simple evolved circuit through co-evolution. In R. Zebulum, D. Gwaltney, G. Horbny, D. Keymeulen, J. Lohn, & A. Stoica (Eds.), (pp. 123-29). IEEE Press. view document
• Hunt, KM, Foster, JA, Forney, LJ, Shuette, UME, Beck, DL, Abdo, A, Fox, LK, Williams, JE, McGuire, MK, and McGuire, MA. "Characterization of the Diversity and Temporal Stability of Bacterial Communities in Human Milk." PLoS ONE 6, no. 6 (2011): e21313. view document.
  
• Imamura, K., & Foster, J. A. (2001). Fault-tolerant hardware throgh n-version genetic programming view document.
• Imamura, K., & Foster, J. A. (2001). Fault-tolerant computing with N-version genetic programming. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, & E. Burke (Eds.), (pp. 178). Morgan Kaufmann. view document.
• Imamura, K., & Foster, J. A. (2001). Fault tolerant computing with n-version genetic programming [international conference on genetic and evolutionary computation]. Morgan Kaufmann. view document.
• imamura, K., & Foster, J. A. (2000). The test vector problem and limitations to evolving digital circuits
• Imamura, K., & Foster, J. A. (2001). Fault-tolerant hardware through n-version genetic programming. (Eds.), view document.
• Imamura, K., & Foster, J. A. (2001). Fault-tolerant computing with N-version genetic programming [international conference on genetic and evolutionary computation]. Morgan Kaufmann. view document.
• Imamura, K., Heckendorn, R. B., Soule, T., & Foster, J. A. (2002). N-version genetic programming via fault masking. (Eds.), LNCS 2278 Springer Verlag. view document.
• Imamura, K., Foster, J. A., & Krings, A. (2000). The test vector problem and limitations to evolving digital circuits. (Eds.), (pp. 81-90). IEEE Press.
• Immamura, K., Soule, T., Heckendorn, R. B., & Foster, J. A. (2003). Behavioral Diversity and a Probabilistically Optimal GP Ensemble. Genetic Programming and Evolvable Machines, 4, 235-53. view document.
• Joyce, P., Fox, L., Casavant, N. C., Wichman, H. A., & Foster, J. A. (2003). Statistical models and methods for analyzing LINE-1 view document.
• Keitzer, M., & Foster, J. A. (2007). Crossover Bias in Genetic Programming. In,Marc Ebner,Michael O'Neill,Aniko Ekart, L. Vanneschi, & A. I. Esparcia-Alcazar (Eds.), Springer Verlag. view document.
• Langdon, W. B., Soule, T., Poli, R., & Foster, J. (1999). The evolution of size and shape. In L. Spector, W. B. Langdon, U.-M. O'Reilly, & P. J. Angeline (Eds.), Advances in Genetic Programming. (pp. 162—191MIT Press.view document.
• Keitzer, M., & Foster, J. A. (2006). The evolution of path length and visitation length in genetic programming view document.
• Masner, J., & Foster, J. A. (1999). Impact of size, representation and robustness in eovlved sorting networks view document.
• Masner, J., Cavalieri, J., Frenzel, J., & Foster, J. A. (1999). Representation and robustness for evolved sorting networks. (Eds.), (pp. 255-61). IEEE Press. view document.
• Meysenburg, M., & Foster, J. A. (1999). Random number generator and GP performance. (Eds.), (pp. 1121-26). Morgan Kaufmann. view document.
• Meysenburg, M., & Foster, J. A. (1999). Random number generator and GA performance, revisited. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, & R. E. Smith (Eds.), (pp. 425-32). Orlando, FL: Morgan Kaufmann. view document.
• Meysenburg, M. M., Hoelting, D., McElvain, D., & Foster, J. A. (2002). How random generator quality impacts genetic algorithm performance. In W. B. Langdon, E. Cantú-Paz, K. E. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, R. Günter, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. K. Burke, & N. Jonoska (Eds.), (pp. 480-83). Morgan Kaufmann. view document.
• Rylander, B., & Foster, J. A. (2000). GA-Hard problems [International conference on genetic and evolutionary computation]. view document.
• Rylander, B., & Foster, J. A. (2001). Genetic algorithms and hardness. In N. Mastorakis, E. (Ed.), (pp. 323-29). World scientific and engineering society press. view document.
• Rylander, B., & Foster, J. A. (2001). Computational complexity and genetic algorithms. In N. Mastorakis, E. (Ed.), (pp. 248-360). World scientific and engineering society press. view document.
• Rylander, B., & Foster, J. A. (2000). How solution space blandness correlates to difficulty in solving the maximum clique problem for genetic algorithms view document.
• Rylander, B., Soule, T., Foster, J. A., & Alves-Foss, J. (2000). Quantum genetic algorithms. (Eds.), (pp. 373). view document.
• Rylander, B., Soule, T., & Foster, J. A. (2001). Quantum Evolutionary Programming. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, & E. Burke (Eds.), (pp. 1005-11). Morgan Kaufmann. view document.
• Hunter, S. S., Settles, M., Foster, J. A., Stenkamp, D. L., & Robison, B. (2004). Generating gene co-expression networks from zebrafish microarray dataGenerating gene co-expression networks from zebrafish microarray data view document.
• Schütte, U., Abdo, Z., A, F. J., Ravel, J., Bunge, J., & Solheim, B. (2010). Bacterial diversity in a glacier foreland of the High Arctic. Molecular Ecology, view document.
• Sheneman, L. (2002). A survey of specialized processor architectures applied to biological sequence alignment view document.
• Sheneman, L. (2005). A survey of evolutionary crossover operators as applied to phylogenetic inferencing view document.
• Sheneman, L., & Foster, J. A. (2003). EVALYN: Evolving Guide Trees for Progressive Multiple Sequence Alignment [Biology 545 poster session]. Moscow:
• Sheneman, L., & Foster, J. A. (2003). Evolving Better Alignments [COBRE External Advisory Board meeting]. Moscow:
• Sheneman, L., & Foster, J. A. (2004). Evolving Better Alignments [Pacific Symposium on Biocomputing]. Hawaii: World Scientific.
• sheneman, L., & foster, J. A. (2006). Estimating the destructiveness of crossover on binary tree representations. (Eds.), Seattle, Wa.: view document.
• sheneman, L., & Foster, J. A. (2007). Eliminating Dynamic Programming Bias in Multiple Sequence Alignment Algorithms view document.
• Sheneman, L., & Foster, J. A. (2004). Evolving Better Multiple Sequence Alignments
• Sheneman, L., & Foster, J. A. (2004). Eliminating dynamic programming bias in multiple sequence alignment algorithms view document.
• Sheneman, L., & Foster, J. A. (2004). Evolving better multiple sequence alignments. In K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. A. Foster, M. Harman, O. Holland, P. L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, & A. Tyrrell (Eds.), LNCS 3102 (pp. 449-60). Seattle, WA: Springer Verlag. view document.
• Sheneman, L., H. Wichman, J. Sullivan, & J. A. Foster. (2003). Generating MSA Algorithm Test Cases by Manipulation of Real Mitochondrial DNA Sequences Moscow:
• Sheneman, L., Evans, J., & Foster, J. A. (2006). Clearcut: the reference implementation for the relaxed neighbor joining phylogenetic tree construction method. Bioinformatics, 15(22)(22), 2823-24. view document.
• Shoaf, J., & Foster, J. A. (1996). A genetic algorithm solution to the efficient set problem: a technique for portolio seleciton based on the Markowitz model. (Eds.), II (pp. 571-73). view document.
• Shyu, C. (2003). MiCA: Administration manual view document.
• Shyu, C., & Foster, J. A. (2003). Inferring Microbial Community Structures with Dynamic Programming and Bayesian Statistics. (Eds.), (pp. 18-22). view document.
• Shyu, C., & Foster, J. A. (2003). Evolving concensus sequence for multiple sequence alignment with a genetic algorithm. In E. Cantú-Paz, J. A. Foster, K. Deb, L. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. K. Standish, G. Kendall, S. W. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. A. Dowsland, N. Jonoska, & J. F. Miller (Eds.), LNCS 2724 (pp. 2298-309). Springer. view document.
• Shyu, C., & Foster, J. A. (2004). Characterization of Microbial Diversity Based on T-RFLP Data with Nonparametric Statistics. (Eds.),
• Shyu, C., & J. A. Foster. (2004). Nonparametric Statistical Approaches for Inferring Microbial Community Structures Based on Terminal Restriction Fragment Length Polymorphisms (T-RFLP) World Scientific.
• Shyu, C., & Foster, J. A. (2001). MiCA: A Web-Based Tool for the Studies of Microbial Community Based on T-RFLP Data view document.
• Shyu, C., & Foster, J. A. (2001). Evolutionary approach for inferring phylogenetic trees view document.
• Shyu, C., Foster, J. A., & Forney, L. J. (2003). Inferring Microbial Community Structures With Dynamic Programming and Bayesian Statistics. (Eds.), view document.
• Shyu, C., Shütte, U., Bent, S. J., Foster, J. A., & Forney, L. J. (2005). Effect of flourophores on electrophoretic mobility of labeled DNA view document.
• Shyu, C., Bent, S., Foster, J. A., & Forney, L. J. (2001). analysis of tRFLP profiles view document.
• Shyu, C., Soule, T., Bent, S. J., Foster, J. A., & Forney, L. J. (2007). MiCA: A Web-Based Tool for the Analysis of Microbial Communities Based on Terminal-Restriction Fragment Length Polymorphisms of 16S and 18S rRNA Genes. Journal of Microbial Ecology, 53(4)(4), 562-70. view document.
• Shyu, C., Sheneman, L., & Foster, J. A. (2004). Evolutionary computation for multiple sequence alignment. Genetic Programming and Evolvable Machines, 5(2)(2), 121-44. view document.
• Shyu, C., Shütte, U., Bent, S., Forney, L. J., & Foster, J. A. (2006). Effect of Fluorophores on the Electrophoretic Mobility of Labeled DNA in the Analysis of Terminal Restriction Fragment Length Polymorphisms of 16S rRNA Genes view document.
• Shyu, C., Shütte, U., Bent, S., Forney, L. J., & Foster, J. A. (2007). Effect of Fluorophores on the Electrophoretic Mobility of Labeled DNA in the Analysis of Terminal Restriction Fragment Length Polymorphisms of 16S rRNA Genes view document.
• Shyu, C., Foster, J. A., Liao, K. X., Bent, S., Sales, K., Forney, L. J. et al. (2002). Microbial community analysis (MiCA): Web-based computational tools for the analysis of microbial community structure and composition based on terminal fragment length polymorphism (T-RFLP) of 16S rRNA genes. (Eds.), (pp. 462). view document.
• Shyu, C., Foster, J. A., Liao, K. X., Bent, S. J., Sales, K., Forney, L. J. et al. (2002). Computational methods for the analysis of microbial community structure and composition. (Eds.), (pp. 461). view document.
• Snevily, H. S., & Foster, J. A. (2000). The 2-pebbling property and a conjecture of Graham's. Graphs and Combinatoriecs, 16, 231-44. view document.
• Soule, T., & Foster, J. (1998). Limiting code growth in genetic programming. J. Evolutionary Computation, 6(4)(4), 293—310.
• Soule, T., Foster, J. A., & Dickinson, J. (1996). Using genetic programming to approximate maximum cliques. In J. Koza, D. E. Goldberg, & a. R. Fogel (Eds.), (pp. 400-05). Morgan Kaufmann.
• Zhou, X., Brown, C. J., Davis, C., Abdo, Z., Hansmann, M., Joyce, P. et al. (2007). Differences in the composition of vaginal microbial communities found in healthy Caucasian and Black women. International Society for Microbial Ecology Journal, 1(2)(2), 121-33. view document.
• Zhou, X., Brown, C. J., Davis, C., Abdo, Z., Hansmann, M., Joyce, P. et al. (2006). Disparity in the vaginal microbial community composition of healthy Caucasian and Black women view document.
• Beck, D., & Settles, M. (2011). OTUBase: an R infrastructure package for taxonomic unit data. Bioinformatics
• Silva, S., Foster, J. A., Nicolau, M., Machado, P., & Giacobini, M. (Eds.). (2011). Genetic Programming. (Vol. LNCS 6621). Torino, Italy: Springer. Document here
• KM Hunt, JA Foster, LJ Forney, UME Shuette, DL Beck, Z Abdo, LK Fox, JE Williams, MK McGuire, MA McGuire (2011 in Press) Characterization of the Diversity and Temporal Stability of Bacterial Communities in Human Milk. PLOS One
• 3. Norris, V, A Zemierline, P Amar, JN Audinot, P Ballet, E Ben-Jacob, G Bernot, G Beslon, A Cabin, E Fanchon, J-L Giavitto, N Glade, P Greussay, Y Grondin, JA Foster, G Hutzler, F Kepes, O Michel, F Molina, J Signorini, P Stano, and AR Thierry (2011 in press) Computing with bacterial constituents, cells and populations: from bioputing to bactoputing. Theory in Biosciences.
• Day, M, Beck D, Foster JA (2011 in press) Microbial Communities as Experimental Units. Bioscience.

Public Talks

I have given several talks for the general public, and even more for scientific audiences. Here are slides from some of these talks.

I teach (or have taught) classes in bioethics, bioinformatics, computational biology, evolutionary computation, theory of computation, design and analysis of algorithms, computational complexity, and just about everything else.

I have taught most courses in the computer science curriculum, with a particular emphasis and depth in theoretical computer science (computability and complexity). I have also taught bioethics for freshmen as part of the UI core curricula for many years.

These are classes I have taught in the past. These links age, and some may not be reliable. Caveat emptor!

I have also taught various independent studies and seminars, which may not be listed here.

I am currently developing courses on computational skills for biologists.

Public Talks

I have given several talks for the general public, and even more for scientific audiences. Here are slides from some of these talks.