Mathematics in Science and Engineering Algebraic and Combinatorial Computational Biology Mathematics in Science and Engineering Algebraic and Combinatorial Computational Biology Edited by Raina Robeva Matthew Macauley Series Editor Goong Chen AcademicPressisanimprintofElsevier 125LondonWall,LondonEC2Y5AS,UnitedKingdom 525BStreet,Suite1650,SanDiego,CA92101,UnitedStates 50HampshireStreet,5thFloor,Cambridge,MA02139,UnitedStates TheBoulevard,LangfordLane,Kidlington,OxfordOX51GB,UnitedKingdom Copyright©2019ElsevierInc.Allrightsreserved. Nopartofthispublicationmaybereproducedortransmittedinanyformorbyanymeans, electronicormechanical,includingphotocopying,recording,oranyinformationstorageand retrievalsystem,withoutpermissioninwritingfromthepublisher.Detailsonhowtoseek permission,furtherinformationaboutthePublisher’spermissionspoliciesandourarrangements withorganizationssuchastheCopyrightClearanceCenterandtheCopyrightLicensingAgency, canbefoundatourwebsite:www.elsevier.com/permissions. Thisbookandtheindividualcontributionscontainedinitareprotectedundercopyrightbythe Publisher(otherthanasmaybenotedherein). Notices Knowledgeandbestpracticeinthisfieldareconstantlychanging.Asnewresearchandexperience broadenourunderstanding,changesinresearchmethods,professionalpractices,ormedical treatmentmaybecomenecessary. Practitionersandresearchersmustalwaysrelyontheirownexperienceandknowledgein evaluatingandusinganyinformation,methods,compounds,orexperimentsdescribedherein.In usingsuchinformationormethodstheyshouldbemindfuloftheirownsafetyandthesafetyof others,includingpartiesforwhomtheyhaveaprofessionalresponsibility. Tothefullestextentofthelaw,neitherthePublishernortheauthors,contributors,oreditors, assumeanyliabilityforanyinjuryand/ordamagetopersonsorpropertyasamatterofproducts liability,negligenceorotherwise,orfromanyuseoroperationofanymethods,products, instructions,orideascontainedinthematerialherein. LibraryofCongressCataloging-in-PublicationData AcatalogrecordforthisbookisavailablefromtheLibraryofCongress BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN978-0-12-814066-6 ForinformationonallAcademicPresspublications visitourwebsiteathttps://www.elsevier.com/books-and-journals Publisher:CandiceJanco AcquisitionEditor:ScottJ.Bentley EditorialProjectManager:KaterinaZaliva ProductionProjectManager:SwapnaSrinivasan CoverDesigner:VictoriaPearson TypesetbySPiGlobal,India Contributors Numbersinparenthesesindicatethepagesonwhichtheauthors’contributionsbegin. BorisAguilar(147),InstituteforSystemsBiology,Seattle,WA,UnitedStates OlcayAkman(351),IllinoisStateUniversity,Normal,IL,UnitedStates RobertBrijder(61),DepartmentWET-INF,HasseltUniversity,Diepenbeek,Belgium TimothyComar(351),BenedictineUniversity,Lisle,IL,UnitedStates Carsten Conradi (279), Hochschule für Technik und Wirtschaft Berlin, Berlin, Germany CarinaCurto(213,241),DepartmentofMathematics,ThePennsylvaniaStateUniver- sity,UniversityPark,PA,UnitedStates Robin Davies (89,375), Biomedical Sciences, Jefferson College of Health Sciences, Roanoke,VA,UnitedStates Joanna Ellis-Monaghan (35), Department of Mathematics, Saint Michael’s College, Colchester,VT,UnitedStates Stefan Forcey (319), Department of Mathematics, University of Akron, Akron, OH, UnitedStates UrmiGhosh-Dastidar(375),DepartmentofMathematics,NewYorkCityCollegeof Technology,Brooklyn,NY,UnitedStates JosselynGonzales(351),IllinoisStateUniversity,Normal,IL,UnitedStates Gabriela Hamerlinck (319), QUBES, BioQUEST Curriculum Consortium, Boyds, MD,UnitedStates Hendrik Jan Hoogeboom (61), Department of Computer Science (LIACS), Leiden University,Leiden,TheNetherlands DanielHrozencik(351),ChicagoStateUniversity,Chicago,IL,UnitedStates Andy Jenkins (89), Department of Mathematics, University of Georgia, Athens, GA, UnitedStates NatašaJonoska(35,61),DepartmentofMathematicsandStatistics,UniversityofSouth Florida,Tampa,FL,UnitedStates JohnJungck(1),UniversityofDelaware,Newark,DE,UnitedStates Logan Keefe (319), Department of Mathematics, Kent State University, Kent, OH, UnitedStates Debra Knisley (1), Department of Mathematics and Statistics, East Tennessee State University,JohnsonCity,TN,UnitedStates xi xii Contributors Jeff Knisley (375), Department of Mathematics and Statistics, East Tennessee State University,JohnsonCity,TN,UnitedStates Matthew Macauley (89,175), School of Mathematical and Statistical Sciences, ClemsonUniversity,Clemson,SC,UnitedStates KatherineMorrison(241),SchoolofMathematicalSciences,UniversityofNorthern Colorado,Greeley,CO,UnitedStates David Murrugarra (147), Department of Mathematics, University of Kentucky, Lexington,KY,UnitedStates Greta Pangborn (1,35), Department of Computer Science, Saint Michael’s College, Colchester,VT,UnitedStates CasianPantea(279),WestVirginiaUniversity,Morgantown,WV,UnitedStates MandaRiehl(1),DepartmentofMathematics,Rose-HulmanInstituteofTechnology, TerreHaute,IN,UnitedStates Masahico Saito (61), Department of Mathematics and Statistics, University of South Florida,Tampa,FL,UnitedStates Widodo Samyono (375), Department of Mathematics, Jarvis Christian College, CharlesA.MeyerScienceandMathematicsCenter,Hawkins,TX,UnitedStates WilliamSands(319),DepartmentofComputationalMathematics,Science,andEngi- neering,MichiganStateUniversity,MI,UnitedStates BrandilynStigler(175),DepartmentofMathematics,SouthernMethodistUniversity, Dallas,TX,UnitedStates Alan Veliz-Cuba (213), Department of Mathematics, University of Dayton, Dayton, OH,UnitedStates Emilie Wiesner (1), Department of Mathematics, Ithaca College, Ithaca, NY, United States NoraYoungs(213),DepartmentofMathematicsandStatistics,ColbyCollege,Water- ville,ME,UnitedStates Preface Whenamathematicianorbiologisthearstheterm“mathematicalbiology,”the mental picture that comes to mind for many may be that of calculus-based techniques such as differential equations. There is, of course, much more of a diversity than this, though other types of mathematical biology often live under an umbrella with a different name. For example, many problems and techniquesinvolvingdiscretemathematicshavebeenrelegatedtotheworldof bioinformatics.Anotherlargeareaofmathematicalworkinthelifesciencesis biostatistics,andyetanotheroneemergingmorerecentlyisdatascience.Indeed, thelinesbetweenthesefieldsareblurredandsubjective.Anareathatinvolves mathematicsandbiologymaybeconsideredmathematicalbiologytosomebut not to others. Some research projects blend so many different fields that it is unnatural to separate into distinct silos such as “mathematics,” “genomics,” “computational biology,” etc. Rather, they are true transdiscplinary science problems: a project on epidemiology might draw from applied mathematics, biology, public health, statistics and data science, computer science, network science, and economics; a project in phylogenetics might involve researchers from mathematics, computer science, a number of fields in biology, statistics, data science, and genomics; and a research group working on protein folding mightconsistofbiologists,biochemists,biophysicists,mathematicians,statisti- cians,andcomputerscientists. Early work involving discrete and algebraic methods to model biological systemscanbetracedbackto(atleast)the1960s.In1969,theoreticalbiologist Stuart Kauffman proposed modeling gene regulatory network with Boolean functions. Around the same time, biologist René Thomas pursued a similar modeling framework that he called “logical models.” These types of models have been studied since under different names, such as Boolean networks, automata networks, generalized cellular automata, and others. In some cases, the models are not Boolean, but ternary, or feature a larger state space. If the state space is a finite field (if not, one can just expand it until it is), then the individual functions describing the model are polynomials. This opens a door tousingtherichtoolbox ofcomputational algebraforanalyzing suchnetwork models, leading to the province of Algebraic Biology. Among the many other exampleswherediscretemathematicsandalgebrafacilitateprogressinmodern biology are the field of Algebraic Statistics that has proved instrumental for a numberofproblemsingenomicsandphylogenetics. xiii xiv Preface Onehallmarkoftransdisciplinaryresearchisthatitsresultsandsubsequent publications could not have been produced only by expertise from a subset of theparticipatingdisciplines.Thisisafarcryfromsomemultidisciplinarywork whereresearchersfromeachdisciplinemayworksomewhatindependentlyon individual “modules,” then write separate sections for the project report and subsequent publication. Transdisciplinary research is also a powerful catalyst foracceleratingadvancementforeachoftheindividualdisciplines.Inbiology, theadventofhigh-throughputtechnologyinthelate20thandearly21stcentury such as gene sequencers, RNA-Seq, and CRISPR, along with the rise of high- performancecomputing,hasputthisdisciplinefirmlyinthespotlightasaprime fieldtobetransformedbymathematicsandtechnology.In2004,biologistJoel Cohenfamouslypredictedthatthisisatwo-wayprocesswhenhepublishedthe paper titled “Mathematics is biology’s next microscope, only better. Biology is mathematics’ next physics, only better.” The following year, mathematician BerndSturmfelsaskedinthetitleofapaperhewrote“Canbiologyleadtonew theorems?,”andthenproceededinthebodyofthepapertoanswerandsupport thisclaimintheaffirmative. The purpose of this book is to highlight some of the new areas of math- ematical biology with combinatorial and algebraic flavors and a distinct com- putational/statistical component. It is in no way meant to be comprehensive, and reflects the personal preferences of the editors to highlight current trends in the discipline. Most importantly, the book reflects our efforts to address the urgentneedtoconnectongoingadvancesindiscreteandalgebraicmathematical biology with the academic curriculum where calculus-based methods still dominate the landscape. While the use of modern algebraic methods is now inthemainstreamofmathematicalbiologyresearch,thistrendhasbeenslowto influencethetraditionalmathematicsandbiologycurricula.Studentsinterested in mathematical biology have relatively easy access to courses that utilize classical analytic methods based on difference and differential equations. By contrast,studentsinterestedinalgebraicanddiscretecomputationalapproaches havefewerdoorsvisiblyopentothem,andindeedmaynotevenknowthatthey exist.Severalhigh-profilenationalreportshaveurgedthemathematicalbiology communitytoenactstepstobridgethisgap,1 andsince2013,theeditorshave collaboratedwithgroupsoflike-mindedfacultytomakeheadwaysinaddressing this problem. Together, we have led several professional faculty development workshops—attheMathematicalBiosciencesInstituteattheOhioStateUniver- sity(2013)andtheNationalInstituteforMathematicalandBiologicalSynthesis (NIMBioS) at the University of Tennessee (2014 and 2016)—focused on developing, disseminating, and classroom-testing novel educational materials based on cutting-edge research in discrete and combinatorial mathematical 1.ThereportVisionandchangeinundergraduatebiologyeducation:acalltoactionofAmerican AssociationfortheAdvancementofScience(2011)andtheNationalResearchCouncil’sreport TheMathematicalSciencesin2025(2013)arejusttwoexamples. Preface xv biology. In fact, this book could be viewed as the third publication in a series thathasbeenlinkedwiththoseworkshops. The first book, titled Mathematical Concepts and Methods in Modern Biology: Using Modern Discrete Models and published in 2013, was edited by Raina Robeva and Terrell Hodge. Topics include Boolean networks, agent- based,andneuronalmodels,linearalgebramodelsofpopulationsandmetabolic pathways, hidden Markov models in genetics, and geometric approaches in phylogenetics. The second publication, Algebraic and Discrete Mathematical Methods for Modern Biology, edited by Raina Robeva and published in 2015, covers topics from graph theory in systems biology, ecology, and evolution, moretopicsonBooleannetworks,Petrinets,epidemiologyonnetworks,linear algebraicapproachesingeneticsandmetabolicanalysis,computationalphylo- genetics, and RNA folding. Most of the material in these books is accessible toundergraduateswhohavenotnecessarilytakencalculus.Inadditiontobeing idealforundergraduates,thesebookscanprovidedetailedintroductionstothe topics for biologists who have limited or even no calculus background. The current “Volume 3” explores a new set of topics with a distinct computational flavor, either not covered in the previous two, or topics that have emerged as fundamentaltothefieldinthelastfewyears.Althoughourtargetaudiencethis time is primarily graduate students, we have made every effort to keep most of the topics accessible to advanced undergraduates as well. All three books are filled with examples and exercises to promote their use in the classroom, andfeaturenotesontheuseofspecializedsoftwareforcomputation,analysis, and simulation. The chapters are designed to be largely independent from one another and can be viewed as starting points for undergraduate research projectsorasentrywaysforgraduatestudentsandresearchersnewtothefield of algebraic mathematical biology. They can also be used as “modules” for classroomuseandindependentstudies.Solutionguidescontainingthesolutions tomostexercisesarealsoavailable. The chapters of this volume are organized to highlight several common themes. We begin with a chapter on multiscale modeling, with a focus on the molecular level, followed by two chapters on the assembly of DNA. Chapters4–6 involve topics on discrete models of the dynamics of molecular networks. More specifically, Chapter 4 introduces the local modeling frame- work, which attempts to clarify and unify a number of modeling paradigms, includingBooleannetworks,logicalmodels,andautomatanetworks.Chapter5 considers these systems with stochastic features, which are sometimes called StochasticDiscreteDynamicalSystems. Chapter 6 looks at the question of reverse engineering the wiring dia- gram,usingtechniquesfromcombinatorialcommutativealgebraandalgebraic geometry—namely Stanley-Reisner theory and the primary decomposition of square-free monomial and pseudomonomial ideals. Though Chapter 7 is on a problem from neuroscience, it also involves the same underlying algebraic framework as Chapter 6. The concept of a pseudomonomial ideal, as far as xvi Preface we can tell, had not been studied until it arose recently in several diverse areas in mathematical biology, from reverse engineering molecular networks to encoding the structure of place fields in neuroscience. Researchers are now studyingandpublishingontheseobjectsandonso-called“neuralideals.”This is a prime example of how biology is leading to new theorems, as predicted by Sturmfels. The neuroscience topic continues into Chapter 8 on threshold linear ODE models over graphs—a framework now used as a simple model of firing patterns in neurons. A central theme in this chapter is how to deduce thedynamicsofthesystemfromthestructureoftheunderlyinggraph. The focus of Chapter 9 is on multistationarity in biochemical reaction networks.Althoughthistopicmayappearunrelated,theaforementionedtheme ofconnectinglocalnetworkstructuretoglobalsystemdynamicsemergesonce again, after being introduced in Chapter 4, and being an underlying theme of Chapter8.Thisquestionhasappearedthroughoutthedecadesindifferentforms. Back in the 1980s, René Thomas posed these questions both in the context of logical models (recall, a variant of Boolean networks), which were popular models of gene networks, and in continuous differential equation frameworks. Heobservedthatasaruleofthumb,positivefeedbackisanecessarycondition forhavingmultiplesteadystates(multistationarity),butnegativefeedbackloops are necessary for cyclic attractors, and hence homeostasis. These conjectures have since been formalized and proven in a number of settings, from discrete modelstodifferentialequations. Chapter 10 is on optimization and linear programming in phylogenetics, where the problem to infer and interpret a phylogenetic tree is useful in multiplecontextsinbiologyandmedicine.Finally,Chapters11and12examine classificationinbiologythroughclusteringandmachinelearning,withexamples rangingfromproteinfamiliestoenvironmentalsystems. This book would not have been possible without the dedicated team of authorswhofeltpassionatelyaboutthevalueofpresentingtheirresearchresults in a way that provides hands-on practical knowledge for readers ranging from advanced undergraduate students to researchers entering the field of algebraic andcomputationalbiology.Wearegratefulfortheirpatienceduringtheediting process and for their willingness to go through multiple revisions with us. We warmly appreciate the support of NIMBioS for the 2016 workshop Discrete andAlgebraicMathematicalBiology:ResearchandEducation.Workonmany of the chapters in this volume started during this workshop and may not have materialized otherwise. Our personal thanks go to Katerina Zaliva, our Editorial Project Manager, who was gracious with her time, prompt to answer questions,andreadytoadoptacheerfulattitudeduringsomeoftheunavoidable challenges in the process. Finally, we thank our spouses, Catherine Gurri and BorisKovatchev,fortheirpatienceandsupportthroughout. MatthewMacauley RainaRobeva August27,2018