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 SchmittWaterman 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, knoncrossing and knonnesting partitions. It turns out that the IstrailLam 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 contextfree grammar approach to study extended RNA secondary structures. Based on the bijection given by ChenDengDuStanleyYan, Jin, Qin and Reidys obtained a formula for the number of knoncrossing 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, mregular linear stacks (and extended mregular 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 ChenDengDu reduction operation on regular noncrossing partitions, we find two equations satisfied by the generating functions of mregular linear stacks and extended mregular linear stacks, respectively. This completes the enumeration of stacks for the 2D square lattice. In particular, a 2regular linear stack is just an extended RNA secondary structure. Barcucci, Pergola, Pinzani and Rinaldi obtained the generating function for hillfree Motzkin paths, which correspond to 2regular 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 3regular simple queues.
