DMS/NIGMS 2: Enumerative combinatorics of phylogenetic trees and networks

Stanford University, Stanford CA

Investigators

Abstract

This project develops combinatorial mathematics for new biological concepts that have emerged from genomic studies of phylogenetic trees and networks. Phylogenetics—the interpretation and construction of trees and networks that describe relationships of shared descent from common ancestors—is central throughout the entire field of biology, contributing to biological subfields in areas as varied as developmental biology, ecology, evolution, genetics, microbiology, and the biology of cancer. The research advances the fundamental understanding of mathematical structures that underlie descent relationships of cells, species, and strains for multifarious biological applications. The project develops the mathematical area of phylogenetic enumerative combinatorics at the intersection of mathematics and biology, toward performing classifications of new discrete combinatorial structures that relate to phylogenetic trees and networks. The project performs unified enumerative studies of several objects, advancing an approach for mathematical analysis of novel phylogenetic combinatorial structures. The structures that will be investigated include: the “perfect phylogenies” that appear in contexts involving genetic recombination and algorithmic improvements in phylogenetic computation; the “galled trees” and “rankable tree-child networks” that assist in extending trees to include biological processes of hybridization and horizontal gene transfer; the “ancestral configurations” that arise from consideration of genetic lineages descending through speciation events; and encodings of trees for phylogenetic analysis of pathogen strains. Its combinatorial analysis proceeds by a shared multidisciplinary framework linking biological structures with methods from the fields of enumerative combinatorics, analysis-of-algorithms, and analytic combinatorics, employing lattice theory, recurrences, generating functions, asymptotic growth analysis, and correspondences with existing combinatorial structures. The project strengthens linkages between mathematics and biology, advancing the mathematics that undergirds the field of phylogenetics, an area that itself serves as a central unifying topic throughout biology. Further, it promotes interdisciplinary mathematical and biological training at the postdoctoral and PhD levels and advances undergraduate research at the interface of biology and mathematics. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.