Group:Theory Lunch
Title: Phylogenic Network Reconstruction, Grammar Compressed Strings
Speaker: Tiancheng Lou, Shiteng Chen University
Time: 2010-11-04 12:00-2010-11-04 13:30
Venue: FIT 1-222


Title: Phylogenic Network Reconstruction

Abstract: In bioinformatics, to study the evolutionary relationship among a set of species, a common approach is to construct a phylogenetic tree.  However, it is well known that the tree structure may not be powerful to capture some evolutionary events such as hybridization processes and horizontal gene transfer. The concept of phylogenetic tree has been extended to phylogenetic network to model these events. To obtain such a network, we can base on different sets of common genes of the species to construct different phylogenetic trees. Then, merge these trees to form a network. The abstract problem can be regarded as constructing a network according to some criteria from a set of binary trees. We will show how to construct a restricted type (galled and $1$ - articulated) of phylogenetic network.


Title: Grammar Compressed Strings

Abstract: The problem could be summarized as following: given a string in a compressed form, preprocess the compressed form such that queries \what is the i-th character in the string" could be answered efficiently. For grammar compressed string, Bille et al. gave a data structure of O(log L) query time in the RAM model, where L is the length of the string before compression. We gave some lower bounds for this problem in the cell-probe model for grammar compressed string. But the lower bound is not tight.

Short Bio: