TAILIEUCHUNG - Báo cáo toán học: "On the uniform generation of modular diagrams"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On the uniform generation of modular diagrams. | On the uniform generation of modular diagrams Fenix . Huang1 and Christian M. Reidys2 Center for Combinatorics LPMC-TJKLC Nankai University Tianjin 300071 . China 1fenixprotoss@ 2duck@ Submitted May 29 2010 Accepted Dec 1 2010 Published Dec 10 2010 Mathematics Subject Classifications 05A18 Abstract In this paper we present an algorithm that generates k-noncrossing ơ-modular diagrams with uniform probability. A diagram is a labeled graph of degree 1 over n vertices drawn in a horizontal line with arcs i j in the upper half-plane. A k-crossing in a diagram is a set of k distinct arcs i1 jd i2 j2 . ik jk with the property i1 i2 ik j1 j2 jk. A diagram without any k-crossings is called a k-noncrossing diagram and a stack of length Ơ is a maximal sequence i j i 1 j 1 i ơ 1 j ơ 1 . A diagram is ơ-modular if any arc is contained in a stack of length at least Ơ. Our algorithm generates after O nk preprocessing time k-noncrossing ơ-modular diagrams in O n time and space complexity. Keywords k-noncrossing diagram uniform generation RSK-algorithm 1 Introduction A ribonucleic acid RNA molecule is the helical configuration of a primary structure of nucleotides A G U and C together with Watson-Crick A-U G-C and U-G base pairs arcs . It is well-known that RNA structures exhibit cross-serial nucleotide interactions called pseudoknots. First recognized in the turnip yellow mosaic virus in 14 they are now known to be widely conserved in functional RNA molecules. Modular k-noncrossing diagrams represent a model of RNA pseudoknot structures 10 11 that is RNA structures exhibiting cross-serial base pairings. The particular case of modular noncrossing diagrams . RNA secondary structures have been extensively studied 8 12 15 16 17 . A diagram is a labeled graph over the vertex set n 1 . n with vertex degrees not greater than one. The standard representation of a diagram is derived by drawing its THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R175 1 vertices .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học