中文  |  English
学术活动
当前位置 >> 首页 >> 学术活动 >> 2015
Counting Protein Contact Maps and the Combinatorics of Partitions(2pm,Wednesday, July 22 , 2015)
发表时间:2015-07-21 阅读次数:638次

Time: 14:00, Wednesday, July 22, 2015

 

Venue: Room 3208, Teaching Building No. 3, Handan Campus, Fudan University

 

Speaker: 陈永川(William Y. C. Chen

Center for Combinatorics, Nankai University
Center for Applied Mathematics, Tianjin University

 

Title: Counting Protein Contact Maps and the Combinatorics of Partitions

 

Abstract:  The contact map of a protein fold is a graph that represents the patterns of contacts. Goldman, Istrail and Papadimitriou showed that any contact map can be decomposed into at most two stacks and one queue. In 2009, Istrail and Lam proposed the problem of finding Schmitt-Waterman type formulas for stacks and queues. It is quite a coincidence that around the same time, combinatorialists were studying essentially, though not exactly, the same structures, namely, k-noncrossing and k-nonnesting partitions. It turns out that the Istrail-Lam type problems can be formulated in purely combinatorial terms. Such a perspective from biology, at least in theory, leads to unexpected challenges to combinatorics. In this talk, we will discuss some recent results on counting stacks and queues. Schmitt and Waterman derived a formula for the number of RNA secondary structures with a given number of bonds. Höner zu Siederdissen et al. defined extended RNA secondary structures and developed a folding algorithm. Müller and Nebel use a context-free grammar approach to study extended RNA secondary structures. Based on the bijection given by Chen-Deng-Du-Stanley-Yan, Jin, Qin and Reidys obtained a formula for the number of k-noncrossing RNA pseudoknot structures. Moreover, Andersen, Penner, Reidys and Waterman obtained the generating function of RNA pseudoknot structures with genus g. For a protein fold on the two dimension square lattice, we need to consider more general contact maps, such as, m-regular linear stacks (and extended m-regular linear stacks), in which each arc length is at least m with m ≥ 2 and the degree of each vertex is bounded by two (and the degree of each terminal vertex is at most three). By using the Chen-Deng-Du reduction operation on regular noncrossing partitions, we find two equations satisfied by the generating functions of m-regular linear stacks and extended m-regular linear stacks, respectively. This completes the enumeration of stacks for the 2D square lattice. In particular, a 2-regular linear stack is just an extended RNA secondary structure. Barcucci, Pergola, Pinzani and Rinaldi obtained the generating function for hill-free Motzkin paths, which correspond to 2-regular simple queues, namely, queues with each arc length at least 2 and each vertex degree at most 1. By studying Motzkin paths avoiding certain patterns, we obtain the generating function for 3-regular simple queues. 

 

版权所有 复旦大学计算系统生物学中心 技术支持:维程互联
地址:上海市邯郸路220号