Regular Simple Queues of Protein Contact Maps

Area of Science:

• Computational Biology
• Combinatorics
• Graph Theory

Background:

• Protein folds can be modeled as self-avoiding walks on lattices.
• Contact maps represent contact patterns within protein folds.
• Previous work showed 2D lattice contact maps decompose into stacks and queues.

Purpose of the Study:

• To investigate 2-regular and 3-regular simple queues in the context of protein contact maps.
• To establish combinatorial relationships between these queues and Motzkin paths.
• To derive generating functions and asymptotic formulas for these structures.

Main Methods:

• Establishing one-to-one correspondences between queue types and specific Motzkin paths.
• Utilizing recurrence relations for generating functions.
• Applying combinatorial enumeration techniques.

Main Results:

• Demonstrated a bijection between 2-regular simple queues and hill-free Motzkin paths.
• Derived a generating function for Motzkin paths with specific peak properties.
• Showed a correspondence between 3-regular simple queues and pattern-avoiding Motzkin paths.
• Obtained generating functions for both 2-regular and 3-regular simple queues.

Conclusions:

• The study provides a combinatorial framework for analyzing protein folding contact maps.
• New enumeration formulas for specific types of queues and Motzkin paths were derived.
• Asymptotic formulas offer insights into the behavior of these structures.