News Archives

Computational Challenges from the Tree of Life

September 28, 2004

Date: Tuesday September 28, 2004
Time: 11am-12:15pm
Location: Woodward 149

Bernard Moret <moret@cs.unm.edu>
Department of Computer Science University of New Mexico

Abstract: My research has focused for the last 5 years on computational models and methods for reconstructing evolutionary histories, known as phylogenies, from molecular data. The most ambitious phylogenetic project is the"Assembling the Tree of Life" (ATOL) initiative, which aims at reconstructing the evolutionary history of all organisms on the planet -- an estimated 10 to 100 million species. ATOL gives rise to a computational grand challenge: assuming that biologists collect sufficient data about extant species, how will we compute a reconstruction for 10 million species when current methods have problems handling a few hundred species and scale poorly? I lead a project named CIPRES, the goal of which is to establish a Cyber Infrastructure for Phylogenetic Research that will support reconstruction of the Tree of Life. In this talk, I will briefly introduce the biological foundations for phylogenetic analysis, then discuss the computational challenges posed by the ATOL initiative, from the design and validation of computationally useful models of evolution to the actual computation and assessment of the Tree of Life itself. Sophisticated mathematics (combinatorics and statistics), good algorithm design (optimization methods, bounding strategies, scalable data structures), and very careful algorithm engineering and testing methodologies are all required for success.  

Stable Internet Routing Without Global Coordination

Date: Tuesday September 21, 2004
Time: 11am-12:15pm
Location: Woodward 149

Jennifer Rexford <jrex@research.att.com>
 Department of Network Management & Performance AT&T Research Lab

Abstract: The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASes to have conflicting policies that can lead to routing instability. This talk proposes a set of guidelines for an AS to follow in setting its routing policies, without requiring coordination with other ASes. Our approach exploits the Internet's hierarchical structure and the commercial relationships between ASes to impose a partial order on the set of routes to each destination. The guidelines conform to conventional traffic-engineering practices of ISPs, and provide each AS with significant flexibility in selecting its local policies. Furthermore, the guidelines ensure route convergence even under changes in the topology and routing policies. Drawing on a formal model of BGP, we prove that following our proposed policy guidelines guarantees route convergence. We also describe how our methodology can be applied to new types of relationships between ASes, how to verify the hierarchical AS relationships, and how to realize our policy guidelines. Our approach has significant practical value since it preserves the ability of each AS to apply complex local policies without divulging its BGP configurations to others. The end of the talk briefly summarizes follow-up studies that have built on this work. The work described in this talk draws on the papers http://www.research.att.com/~jrex/pape rs/ton01-stable.pdf http://www.research.att.com/~jrex/papers/i nfocom01.ps