Chris Whidden

Simons Foundation Fellow of the
Life Sciences Research Foundation

Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N.
PO Box 19024
Seattle, WA, USA 98109




A picture of me An SPR supertree

Research Interests

An SPR tree space graph

Summary

I'm a Simons Foundation Fellow of the Life Sciences Research Foundation in the Computational Biology program at the Fred Hutchinson Cancer Research Center (FHCRC) in Seattle, WA. I'm interested in developing efficient algorithms and software for NP-hard problems and Big Data, particularly in computational biology. My PhD work sped up the computation of the SPR distance between evolutionary trees, a measure of lateral gene transfer, by several orders of magnitude-hours to seconds. I applied these fast SPR distance computation to build supertrees from thousands of gene trees with hundreds of taxa.

To broaden my scope beyond theoretical research, I chose to come to the FHCRC in order to broaden my contribution to society. My research here will make significant contributions to computational theory, computational practice, and biological investigations. In addition to solving several interesting and difficult theoretical problems related to the "tree space" of Bayesian phylogenetics, I am developing software for constructing SPR tree space graphs. I will use this software to analyze the behaviour of Bayesian phylogenetic methods given missing or conflicting data.

For the biological component, I will analyze data from studies of vaccine response, cancer etiology, and metagenomics at the center. The results will be used to develop new Bayesian phylogenetic methods and guided operators, particularly in the design of ``online'' phylogenetic algorithms that accept data coming in a sequential fashion rather than all-at-once, which will be used to efficiently maintain phylogenies of quickly evolving pathogens such as influenza. These new methods will form the foundation of the next generation of evolutionary inference methods for medically-relevant problems.

Teaching

Summer 2011

Education

August 2013 Doctor of Philosophy (PhD), Dalhousie University, Canada

October 2009: Master of Computer Science (MCSc), Dalhousie University, Canada

May 2008: Bachelor of Computer Science (BCSc) with Co-op and First Class Honours, Dalhousie University, Canada


Publications

Google Scholar profile

Chris Whidden and Frederick A. Matsen IV. Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance. Submitted.

Chris Whidden and Frederick A. Matsen IV. Efficiently Inferring Pairwise Subtree Prune-and-Regraft Adjacencies between Phylogenetic Trees. Submitted.

Alex Gavryushkin, Chris Whidden and Frederick A. Matsen IV. The combinatorics of discrete time-trees: theory and open problems Submitted.

Chris Whidden and Frederick A. Matsen IV. Calculating the Unrooted Subtree Prune-and-Regraft Distance. Submitted.

Chris Whidden and Frederick A. Matsen IV. (2017). Ricci-Ollivier Curvature of the Rooted Phylogenetic Subtree-Prune-Regraft Graph. Theoretical Computer Science. Forthcoming.

Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden, and Norbert Zeh. (2016). Hybridization Number on Three Rooted Binary Trees is EPT. SIAM Journal on Discrete Mathematics. 30(3), 1607-1631. The original publication is available at epubs.siam.org

Julia Matsieva, Steven Kelk, Celine Scornavacca, Chris Whidden, and Dan Gusfield. (2016). A resolution of the static formulation question for the problem of computing the history bound. IEEE/ACM Transactions on Computational Biology and Bioinformatics. Forthcoming.

Chris Whidden and Frederick A. Matsen IV. (2016). Ricci-Ollivier Curvature of the Rooted Phylogenetic Subtree-Prune-Regraft Graph. In: Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO16). 106-120.

Chris Whidden, Robert G. Beiko, and Norbert Zeh. (2015). Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees. Algorithmica. doi: 10.1007/s00453-015-9983-z . The original publication is available at www.springer.com.

Chris Whidden and Frederick A. Matsen IV. (2015). Quantifying MCMC Exploration of Phylogenetic Tree Space. Systematic Biology. 64(3), 472-491. Supplemental material available at datadryad.org.

Chris Whidden, Norbert Zeh, and Robert G. Beiko. (2014). Supertrees Based on the Subtree Prune-and-Regraft Distance. Systematic Biology. 63(4), 566-581. Supplemental material available at datadryad.org.

Eva Boon, Conor J. Meehan, Chris Whidden, Dennis H.-J. Wong, Morgan G.I. Langille, and Robert G. Beiko. (2014). Interactions in the microbiome: communities of organisms and communities of genes. FEMS Microbiology Reviews. 38(1), 90-118. doi: 10.1111/1574-6976.12035

Chris Whidden, Robert G. Beiko, and Norbert Zeh. (2013). Fixed-Parameter Algorithms for Maximum Agreement Forests. SIAM Journal on Computing, 42(4), 1431-1466. The original publication is available at epubs.siam.org.

Chris Whidden, Robert G. Beiko and Norbert Zeh. (2010). Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments. In: Proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010. Lecture Notes in Computer Science, vol. 6049, pp. 141-153. Springer-Verlag (2010). The original publication is available at www.springerlink.com.

Chris Whidden and Norbert Zeh. (2009). A Unifying View on Approximation and FPT of Agreement Forests. Algorithms in Bioinformatics: 9th International Workshop, WABI 2009, Philadelphia, USA, September 12-13, 2009. Proceedings. 390-402. The original publication is available at www.springerlink.com.

Vlado Keselj, Haibin Liu, Norbert Zeh, Christian Blouin, and Chris Whidden. (2009). Finding optimal parameters for edit distance based sequence classification is NP-hard. Proceedings of the KDD'09 Workshop on Statistical and Relational Learning in Bioinformatics, StReBio'09. 17-21.

Tony Abou-Assaleh, Chris Whidden, Vlado Keselj, Hathai Tanta-ngai, and Nick Cercone. (2007). DalTREC 2007 QA System Jellyfish: Experiments with Integration of Lucene and GATE, and Improved Usage of WordNet and Qrel. In The Sixteenth Text REtrieval Conference (TREC 2007), Gaithersburg, Maryland, USA.

Tony Abou-Assaleh, Nick Cercone, Jon Doyle, Vlado Keselj, and Chris Whidden. (2005). DalTREC 2005 QA System Jellyfish: Mark-and-Match Approach to Question Answering. In The Fourteenth Text REtrieval Conference (TREC 2005) Proceedings, Gaithersburg, Maryland, USA.


Technical Reports

Chris Whidden, Robert G. Beiko and Norbert Zeh. (2010). Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments. Dalhousie FCS Technical Report CS-2010-03.

Chris Whidden and Norbert Zeh. (2009). A Unifying View on Approximation and FPT of Agreement Forests. Dalhousie FCS Technical Report CS-2009-02.

Chris Whidden. (2007). Utilizing Automatic Coreference Resolution with the Jellyfish Question Answering System. Dalhousie FCS Technical Report.

Chris Whidden. (2005). Simple and Effective Question Processing using Regular Expressions and WordNet. Dalhousie FCS Technical Report.


Software

rspr
A C++ application for calculating approximate and exact rSPR distances between evolutionary trees. An implementation of the rSPR algorithms from "A Unifying View on Approximation and FPT of Agreement Forests", and the improvements from "Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments". The most recent version requires that one tree is binary and rooted but the other tree may be multifurcating and/or unrooted.

SPR Supertrees
A C++ application for computing supertrees that minimize the SPR distance metric. These supertrees minimize the inferred number of lateral genetic transfer events and can be used to identify "highways" of genetic transfer.

sprspace
Software for computing SPR "tree space" graphs of Bayesian Markov Chain Monte Carlo posterior distributions in order to identify topological peaks and quantify mixing.

curvature
Software for computing the Ricci-Ollivier curvature of the rooted SPR graph and simulating random walks on the graph.

uspr
A C++ application for computing SPR distances between unrooted phylogenetic trees such as those inferred by MrBayes.