JIN Yinglie,REN Junli.Enumeration for ordered trees and its applications[J].Journal of Yanbian University,2019,45(02):114-116，188.
有序树的计数及其应用
- Title:
- Enumeration for ordered trees and its applications
- 文章编号:
- 1004-4353(2019)02-0114-03
- Keywords:
- ordered tree; RNA secondary structure; enumeration
- 分类号:
- O157.1
- 文献标志码:
- A
- 摘要:
- 利用分拆-组装算法,构造了含有k+1个内点的有序树与森林之间的双射,讨论了在某些参数限制条件下的有序树的计数,并在建立RNA二级结构与非标号有序树之间的双射基础上,给出了满足一定参数条件的RNA二级结构计数问题的显示闭公式.
- Abstract:
- We discusses the enumeration of ordered trees under the parameter restrictions by the split-assembly algorithm. Finally we establish a bijection between RNA secondary structures and ordered trees, which is used to enumerate RNA secondary structures under the parameter restrictions, and give the explicit closed formula.
参考文献/References:
[1] WATERMAN M S. Combinatorics of RNA hairpins and cloverleaves[J]. Studies in Applied Mathematics, 1978,60:91-96.
[2] SCHMITT W R, WATERMAN M S. Linear trees and RNA secondary structures[J]. Discrete Applied Mathematics, 1994,51:317-323.
[3] HOFACKER I L, SCHUSTER P, STADLER P F. Combinatorics of RNA secondary structure[J]. Discrete Applied Mathematics, 1998,88:207-237.
[4] LIAO B, WANG T M. General combinatorics of RNA secondary structures[J]. Mathematical Biosciences, 2004,191:69-81.
[5] WANG W W, ZHANG M, WANG T M. Asymptotic enumeration of RNA secondary structure[J]. J Math Anal Appl, 2008,342:514-523.
[6] CLOTE P. Combinatorics of saturated secondary structures of RNA[J]. Journal of Computational Biology, 2006,13:1640-1657.
[7] CHEN W Y C. A general bijective algorithm for trees[J]. Proc Natl Acad Sci USA, 1990,87(24):9635-9639.
[8] LIU C L, WANG Z H. A bijection between ordered trees and bicoloured ordered trees[J]. Discrete Mathematics, 2009,309:1417-1421.
备注/Memo
收稿日期: 2019-05-17
*作者简介: 金应烈(1962—),男,博士,教授,研究方向为组合数学.