Bijective enumeration of general stacks Guo, Qianghui; Jin, Yinglie; Sun, Lisa H. ...
Advances in applied mathematics,
July 2024, 2024-07-00, Letnik:
158
Journal Article
Recenzirano
Odprti dostop
Combinatorial enumeration of various RNA secondary structures and protein contact maps is of great interest for both combinatorists and computational biologists. Counting protein contact maps is much ...more difficult than that of RNA secondary structures due to the significant higher vertex degree. The state of art upper bound for vertex degree in previous works is two. This paper proposes a solution for counting general stacks with arbitrary vertex degree upper bound. By establishing a bijection between such general stacks and m-regular Λ-avoiding DLU-paths, and counting these pattern avoiding lattice paths, we obtain a unified system of equations for the generating functions of the number of general stacks. We further show that previous enumeration results for RNA secondary structures and linear stacks of protein contact maps can be derived from the equations for general stacks as special cases.
Combinatorics of biopolymer structures, especially enumeration of various RNA secondary structures and protein contact maps, is of significant interest for communities of both combinatorics and ...computational biology. However, most of the previous combinatorial enumeration results for these structures are presented in terms of generating functions, and few are explicit formulas. This paper is mainly concerned with finding explicit enumeration formulas for a particular class of biologically relevant structures, say, saturated 2-regular simple stacks, whose configuration is related to protein folds in the 2D honeycomb lattice. We establish a semi-bijective algorithm that converts saturated 2-regular simple stacks into forests of small trees, which produces a uniform formula for saturated extended 2-regular simple stacks with any of the six primary component types. Summarizing the six different primary component types, we obtain a bivariate explicit formula for saturated extended 2-regular simple stacks with n vertices and k arcs. As consequences, the uniform formula can be reduced to Clote's results on k-saturated 2-regular simple stacks and the optimal 2-regular simple stacks, and Guo et al.'s result on the optimal extended 2-regular simple stacks.
In this work, we shall concentrate on the isoperimetric properties of the
k
-degree Cayley graphs
G
k
,
n
, which were proposed recently for building interconnection networks. We shall give the exact ...isoperimetric number
i
(
G
k
,
n
)
when
n
=
2
, and an upper bound of
i
(
G
k
,
n
)
in the general case.
Combinatorial enumeration of various RNA secondary structures and protein contact maps, is of great interest for both combinatorists and computational biologists. Enumeration of protein contact maps ...has considerable difficulties due to the significant higher vertex degree than that of RNA secondary structures. The state of art maximum vertex degree in previous works is two. This paper proposes a solution for counting stacks in protein contact maps with arbitrary vertex degree upper bound. By establishing bijection between such general stacks and \(m\)-regular \(\Lambda\)-avoiding \(DLU\) paths, and counting the paths using theories of pattern avoiding lattice paths, we obtain a unified system of equations for generating functions of general stacks. We also show that previous enumeration results for RNA secondary structures and protein contact maps can be derived from the unified equation system as special cases.
Combinatorics of biopolymer structures, especially enumeration of various RNA secondary structures and protein contact maps, is of significant interest for communities of both combinatorics and ...computational biology. However, most of the previous combinatorial enumeration results for these structures are presented in terms of generating functions, and few are explicit formulas. This paper is mainly concerned with finding explicit enumeration formulas for a particular class of biologically relevant structures, say, saturated 2-regular simple stacks, whose configuration is related to protein folds in the 2D honeycomb lattice. We establish a semi-bijective algorithm that converts saturated 2-regular simple stacks into forests of small trees, which produces a uniform formula for saturated extended 2-regular simple stacks with any of the six primary component types. Summarizing the six different primary component types, we obtain a bivariate explicit formula for saturated extended 2-regular simple stacks with \(n\) vertices and \(k\) arcs. As consequences, the uniform formula can be reduced to Clote's results on \(k\)-saturated 2-regular simple stacks and the optimal 2-regular simple stacks, and Guo et al.'s result on the optimal extended 2-regular simple stacks.
PDF
