The Winifred Asprey Lecture Series in Computer Science

Sponsored by the Department of Computer Science in honor of Winifred Asprey '38 Emeritus Professor of Computer Science

Tiffani Williams, Texas A&M
Tuesday, October 13, 2009, 5pm
OLB, Computer Science 105
Tea reception in Student Lounge at 4:30pm.

Using the MapReduce Framework to Analyze Large Collections of Evolutionary Trees on Multi-Core Platforms

Evolutionary trees represent the genealogical relationships among a collection of organisms. Evolutionary trees have many benefits such as automating species identification, improving global agriculture, and understanding disease transmission. Current techniques to reconstruct the evolutionary tree for a set of organisms can easily produce tens of thousands of potential candidate trees. How can we produce an accurate estimation of the true evolutionary history for the organisms under investigation from such a large collection of trees?

In this talk, I will discuss our MrsRF (MapReduce Speeds up RF) algorithm, which is a multi-core algorithm for computing the all-pairs Robinson-Foulds (RF) distance between evolutionary trees. The novelty of our algorithm lies in how we use the MapReduce framework, which has been popularized by Google, to compare tens of thousands of evolutionary trees quickly on multi-core platforms. The talk will conclude by describing applications that utilize our MrsRF algorithm in order to reconstruct accurate evolutionary trees.


Tiffani L. Williams is an Assistant Professor in the Department of Computer Science at Texas A&M University. She earned her B.S. in computer science from Marquette University and Ph.D. in computer science from the University of Central Florida. Afterward, she was a postdoctoral fellow at the University of New Mexico. Her honors include a Radcliffe Institute Fellowship, an Alfred P. Sloan Foundation Postdoctoral Fellowship, and a McKnight Doctoral Fellowship. Her research interests are in the areas of bioinformatics and high-performance computing.