COLLOQUIUM
Department of Computer Science and Engineering
University of South Carolina

 
Optimal Implementation of UPGMA and 
Neighbor-Joining Algorithms

Duncan A. Buell

Department of Computer Science and Engineering
University of South Carolina

Date: September 20, 2002 (Friday)
Time: 3:30-4:30PM
Place: Swearingen 1A03 (Faculty Lounge)


Abstract

We describe an implementation of the UPGMA (unweighted pair group
using arithmetic averages) algorithm that is widely used in
computational biology.  The implementation is asymptotically optimal
as a PRAM algorithm among all algorithms for computing the tree
produced by UPGMA.
	
Duncan A. Buell received the B. S. and M. A. degrees in mathematics
from the University of Arizona and University of Michigan,
respectively, and in 1976 his Ph. D. in mathematics from the
University of Illinois at Chicago.  He was an assistant and then
associate professor in the Department of Computer Science at Louisiana
State University in Baton Rouge.  In 1986 he joined the Supercomputing
Research Center (now the Center for Computing Sciences), a division of
the Institute for Defense Analyses, doing high performance computing
and computational mathematics research for the National Security
Agency.  He has written two books and more than fifty research papers
in number theory, document and information retrieval, parallel
algorithms, and computer architecture.  While at IDA he was project
manager for the Splash 2 reconfigurable computing project, one of the
first successful ventures into the use of Field Programmable Gate
Arrays (FPGAs) as the programmable "CPU" in what is now known as a
reconfigurable computing machine. He was also one of the co-founders
of the FPGAs for Custom Computing Machines (FCCM) conference held
yearly since 1993.  He joined the University of South Carolina as
Professor and Chair of the Department of Computer Science and
Engineering in October 2000.