UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Stacked graphs and symmetric groups : modelling the conformation space of nucleic acids Roosenmaallen, Morgan Antony 2017

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2017_may_Roosenmaallen_Morgan.pdf [ 3.39MB ]
JSON: 24-1.0343563.json
JSON-LD: 24-1.0343563-ld.json
RDF/XML (Pretty): 24-1.0343563-rdf.xml
RDF/JSON: 24-1.0343563-rdf.json
Turtle: 24-1.0343563-turtle.txt
N-Triples: 24-1.0343563-rdf-ntriples.txt
Original Record: 24-1.0343563-source.json
Full Text

Full Text

Stacked Graphs and Symmetric Groups:Modelling the Conformation Space ofNucleic AcidsbyMorgan Antony RoosenmaallenB.Sc., The University of British Columbia, 2014B.A., Lakehead University, 2009A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Interdisciplinary Studies)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)April 2017©Morgan Antony Roosenmaallen, 2017Thesis CommitteeThe undersigned certify that they have read, and recommend to the College ofGraduate Studies for acceptance, a thesis entitled Stacked Graphs and SymmetricGroups: Modelling the Conformation Space of Nucleic Acids, submitted byMorganAntony Roosenmaallen in partial fulfilment of the requirements of the degree ofMaster of Science:Javad Tavakoli, Barber School of Arts and SciencesSupervisor, ProfessorParamjit Gill, Barber School of Arts and SciencesSupervisory Committee Member, ProfessorYong Gao, Barber School of Arts and SciencesSupervisory Committee Member, ProfessorRobert Lalonde, Barber School of Arts and SciencesUniversity Examiner, ProfessorMonday April 10 2017Date Submitted to Grad StudiesiiAbstractThis work introduces a technique for approximating the conformation space ofrigid and semi-rigid kinematic chains with finite inverse kinematic solutions usinggraph-like constructs called stacked graphs. The technique is developed in the con-text of nucleic acids, in particular ribonucleic acid (RNA), whose phosphate back-bone can be modelled as a kinematic chain. Additionally, a process for identifyingstable RNA conformations and likely conformational pathways is demonstrated.As a secondary result, a potentially novel relationship between stacked graphs andsymmetric groups is uncovered and briefly investigated.iiiA Note on NotationTo facilitate ease of reading as well as to maintain consistency, a standardizednaming and indexing notations will be used. Set hierarchies are denoted by specificcases and font styles푎 ∈ 퐴 ∈  ∈ 픸 ∈ 프where the lowest level element is always indicated by a lower-case English charac-ter. Element indices are denoted by lower-case letters using a right-hand, ‘ascendingcurl’ format, beginning with the elements hierarchical location. For example푎푖 ∈ 퐴 → 푎푖 ∈ 퐴푎푖 ∈ 퐴푗 ∈  → 푎푗푖 ∈ 퐴푗 ∈ 푎푖 ∈ 퐴푗 ∈ 푘 ∈ 픸 → 푎푘 푗푖 ∈ 퐴푘푗 ∈ 푘 ∈ 픸푎푖 ∈ 퐴푗 ∈ 푘 ∈ 픸푙 ∈ 프 → 푎푘 푗푙 푖 ∈ 퐴푙 푘푗 ∈ 푙푘 ∈ 픸푙 ∈ 프.A single term, such as 퐴푙 푘푗 , encodes not only the elements place in a hierarchy, butthe hierarchy’s total depth as well.Two-valued scripts denote start-stop indices, as in the case of graph edges푒푖푗 ∈ 퐸.As numerical index values never exceed 9 in this work, commas between such in-dices will be avoided to condense notation. Thus, 푒17 should be read as 푒1,7. Occa-sionally, indices of (푛 − 1) and the like will be used, producing terms like 푒4(푛−1).Superscripts in the absence of subscripts denote notions of size, such as a groupcomposition of length 푛휋푛and a cycle stack of length 푛 and size 푚푛푚.Graphs with vertex sets 푉 and edge sets 퐸 are denoted by  = (푉 ,퐸). Walks,paths, and cycles are written in edge-edge format. For example푒13 − 푒32 − 푒27. (1)ivA Note on NotationAll indices - vector or script - begin at 0. Vectors are accessed using [⋅] notation.Thus if 푎 = ⟨1, 7,−2, 11⟩, then 푎[1] = 7 and 푎[3] = 11.Lower-case Greek letters are reserved for group theoretic concepts (Chapter3), except in the case of kinematic chain parametrization, where they are used tomaintain consistency with reference works (Chapter 5). Upper-case Greek lettersare reserved for general spaces.vTable of ContentsThesis Committee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiA Note on Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Stacked Graphs . . . . . . . . . . . . . . . . . . . . . . . . 82.1 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Constructing Stacked Graphs . . . . . . . . . . . . . . . . . . . . 132.3 Assignments and Feasibility . . . . . . . . . . . . . . . . . . . . 192.4 Feasibility of Non-Simple Stacked Graphs . . . . . . . . . . . . . 332.5 Singular Constraints . . . . . . . . . . . . . . . . . . . . . . . . . 35Chapter 3: Stacked Graphs and Symmetric Groups . . . . . . . . . . 393.1 Assignments and 핊푚 . . . . . . . . . . . . . . . . . . . . . . . . 393.2 Assignment Feasibility and Symmetric Group Duals . . . . . . . 483.3 Duality and Non-Simple Stacked Graphs . . . . . . . . . . . . . . 54Chapter 4: Linear Programming: Communication, Capacity, andCon-tiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.1 Local, Regional, and Global Optimization . . . . . . . . . . . . . 564.2 The 3C Constraints of Assignment Feasibility . . . . . . . . . . . 57viTABLE OF CONTENTS4.2.1 Communication . . . . . . . . . . . . . . . . . . . . . . . 594.2.2 Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . 604.2.3 Contiguity . . . . . . . . . . . . . . . . . . . . . . . . . 614.2.4 Asinglular LP Problem Statement . . . . . . . . . . . . . 614.2.5 Size Complexity of Asingular LP . . . . . . . . . . . . . 624.3 Modelling Singular Constraints: ULA . . . . . . . . . . . . . . . 64Chapter 5: Kinematic Chains . . . . . . . . . . . . . . . . . . . . . . 685.1 Denavit-Hartenberg Parameters . . . . . . . . . . . . . . . . . . . 685.2 Forward and Inverse Kinematics . . . . . . . . . . . . . . . . . . 725.3 Kinematic Nucleic Acids . . . . . . . . . . . . . . . . . . . . . . 735.4 Outline of Converting IK Solutions and Stacked Graphs . . . . . . 75Chapter 6: Conformation Space Sampling . . . . . . . . . . . . . . . 776.1 Sampling Technique . . . . . . . . . . . . . . . . . . . . . . . . 776.2 Formal Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 82Chapter 7: Stacked Graphs of Conformation Spaces . . . . . . . . . . 957.1 Validating theULAConstraint andDisconnectingAssignment Com-ponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98Chapter 8: Conformation Space Simulations . . . . . . . . . . . . . . 1028.1 Comparing Normalized Workspaces . . . . . . . . . . . . . . . . 1028.1.1 퐴∗ Congruence Metric Ω퐴∗ . . . . . . . . . . . . . . . . 1038.1.2 Vertex Stack Congruence Metric Ω푉 . . . . . . . . . . . 1048.1.3 Regional Congruence Metric Ω . . . . . . . . . . . . . 1058.1.4 Layer Congruence Metric Ω . . . . . . . . . . . . . . . 1078.1.5 Metrics At Infinite Resolutions . . . . . . . . . . . . . . . 1098.1.6 Metrics on Groups of Conformation Graphs . . . . . . . . 1108.2 Averaged Stacked Graphs . . . . . . . . . . . . . . . . . . . . . . 1128.3 Energetics and Simulations . . . . . . . . . . . . . . . . . . . . . 1138.4 Model Validation and Real-World Data . . . . . . . . . . . . . . . 115Chapter 9: Concluding Remarks and Future Research . . . . . . . . 118Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124Appendix A: Constructing Unique Subscripts . . . . . . . . . . . . . . 124Appendix B: Constructing Normal Coordinates . . . . . . . . . . . . . 127viiList of TablesTable 6.1 RNA Phosphate Backbone Bond Lengths . . . . . . . . . 80Table 6.2 RNA Phosphate Backbone Bond Angles . . . . . . . . . . 80Table 6.3 Impact of Bisections on Sample Lattice Grid Length . . . 81Table 6.4 Sample Label Ranges for 푛푐 and 푛푒 . . . . . . . . . . . . . 85Table A.1 Unique Sample Subscripts . . . . . . . . . . . . . . . . . 124viiiList of FiguresFigure 1.1 Types of RNA . . . . . . . . . . . . . . . . . . . . . . . 2Figure 1.2 RNA and DNA . . . . . . . . . . . . . . . . . . . . . . . 3Figure 1.3 Active and Inactive HIV . . . . . . . . . . . . . . . . . . 5Figure 2.1 The Annulus 푓 (푋) and Image Approaches . . . . . . . . 10Figure 2.2 Potential Image Approaches for 푓 (푋) . . . . . . . . . . . 11Figure 2.3 Stacks and Assignments on 푓 (푋) . . . . . . . . . . . . . 12Figure 2.4 Linear Approximation of 푓 (푋) . . . . . . . . . . . . . . 13Figure 2.5 Edge Stack . . . . . . . . . . . . . . . . . . . . . . . . . 14Figure 2.6 Multiple Graph Packings . . . . . . . . . . . . . . . . . 16Figure 2.7 Packed and Unpacked Diagrams . . . . . . . . . . . . . . 18Figure 2.8 Valid and Invalid Edge Stack Assignments . . . . . . . . 20Figure 2.9 Paths of a Path Stack Assignment . . . . . . . . . . . . . 22Figure 2.10 Feasible and Infeasible Assigments of 32 . . . . . . . . 23Figure 2.11 Not All Disjoint Cycle Covers of Cycle Stacks Are Feasi-ble Assignments . . . . . . . . . . . . . . . . . . . . . . 23Figure 2.12 Extension of  (푛−1)푚 to 푛푚 . . . . . . . . . . . . . . . . 25Figure 2.13 Adjacency of 푣0푎 and 푣푛−1푏 . . . . . . . . . . . . . . . . . 26Figure 2.14 Joined Cycle Stacks . . . . . . . . . . . . . . . . . . . . 27Figure 2.15 Assignment Covers of Joined Cycle Stacks of Size 2 . . . 28Figure 2.16 Multi-Joined Cycle Stacks . . . . . . . . . . . . . . . . . 29Figure 2.17 Assignment Covers of Path Stack Connected Cycle Stacksof Size 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 2.18 Regional Stacked Graphs . . . . . . . . . . . . . . . . . 32Figure 2.19 Identity Assignment 퐴∗ . . . . . . . . . . . . . . . . . . 34Figure 2.20 ULA Singular Feasibility Constraint . . . . . . . . . . . 37Figure 3.1 핊푚 Elements as Perfect Matchings . . . . . . . . . . . . 40Figure 3.2 Graph Dual of 휎 . . . . . . . . . . . . . . . . . . . . . . 42Figure 3.3 Group Dual Inverses . . . . . . . . . . . . . . . . . . . . 45Figure 3.4 A Bad Composition . . . . . . . . . . . . . . . . . . . . 46ixLIST OF FIGURESFigure 4.1 Linear Cycle Stacks . . . . . . . . . . . . . . . . . . . . 58Figure 4.2 Communication: Losing Layer Information . . . . . . . . 59Figure 4.3 Communication: Regaining Layer Information . . . . . . 60Figure 4.4 Shared Edge Stacks and LP Complexity . . . . . . . . . . 63Figure 4.5 Independent Optimization and ULA . . . . . . . . . . . . 67Figure 5.1 Examples of Kinematic Pairs . . . . . . . . . . . . . . . 69Figure 5.2 Parallel Kinematic Chain . . . . . . . . . . . . . . . . . 70Figure 5.3 Denavit-Hartenberg Parameters . . . . . . . . . . . . . . 71Figure 5.4 3푅 Chain and its Workspace . . . . . . . . . . . . . . . . 72Figure 5.5 Finite and Infinite IK Solutions . . . . . . . . . . . . . . 73Figure 5.6 Phosphate Backbone as a Kinematic Chain . . . . . . . . 74Figure 5.7 Outline of Modelling Procedure . . . . . . . . . . . . . . 76Figure 6.1 Chain Parameters and Workspace Extent . . . . . . . . . 78Figure 6.2 ComparingConformation SpacesUnderDifferent Parametriza-tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79Figure 6.3 Cartesian Component Sample Labelling . . . . . . . . . 83Figure 6.4 Adjacency on Variable-Scale Lattice Graph . . . . . . . . 87Figure 6.5 Sample Adjacency . . . . . . . . . . . . . . . . . . . . . 88Figure 6.6 Conformational Pathways . . . . . . . . . . . . . . . . . 91Figure 7.1 Annulus Function 푓 (푋) Revisited . . . . . . . . . . . . . 100Figure 7.2 Disconnecting Annulus Components . . . . . . . . . . . 101Figure 8.1 Regional Identification . . . . . . . . . . . . . . . . . . . 106Figure 8.2 Layer Identification . . . . . . . . . . . . . . . . . . . . 108Figure 8.3 Lattice Grouping Technique for Real-World Sample Data 116Figure A.1 Construction of Unique Sample Subscripts using Spirals . 126xAcknowledgementsI would like to thank my supervisor Javad Tavakoli for his assistance and pa-tience in what has been a lengthy endeavour, as well as Al Vaisius for introducingme to the research topic some four or five years ago.xiChapter 1IntroductionRibonucleic acid, or RNA, is a complex, polymeric biomolecule which per-forms a wide range of cellular functions. For example, messenger RNA (mRNA)synthesized from a DNA template is the mechanism for translating the nucleotidecodons into the amino acid sequences of proteins (Figure 1.1(a)) [LNC93]. In thisprocess, RNAmolecules are structural components of ribosomes, which are the siteof nascent protein synthesis; as well transfer RNA (tRNA) forms covalent bondswith amino acids to deliver them to ribosomes (Figure 1.1(b)) [LNC93]. In ad-dition, there are a myriad of small regulatory RNAs that control gene expression.There also exists viral RNA (vRNA), which is used by a number of viruses forgenetic information instead of DNA (Figure 1.1(c)) [LNC93].RNA and DNA are similarly constructed from long sequences of nucleotidesand shares many of the same chemical structures, including a phosphate backbone(Figure 1.2). The functionality of a given RNA strand is greatly influenced by itsparticular conformation, or the bending, twisting, and folding of the strand aboutitself and other biomolecules1. The phosphate backbone provides the primary levelof constraints for RNA conformation. Although the backbone chain of nucleic acidsconsists entirely of sigma bonds, i.e. single covalent bonds, with full rotation aboutthe bonds, the lengths of atomic bonds in the backbone, as well as the angles be-tween them, place strong limits on how a single nucleotide moves. An important -and still open - question concerning RNA functionality is the exact nature of theselimits with regards to neighboring polymeric units.Considerable research efforts have gone into studying the conformation prob-lem [Mak08][KHP11][WKM+08][MLL08]. Loosely stated, the issue is how therotation of a nucleotide about the chemical bonds in its backbone relates to thephysical space the backbone exists in. More formally, the challenge is to find thepre-image of푓 ∶ [0◦, 360◦)6 → ℝ3 × [0◦, 360◦)3 (1.1)where 푓 is a known function.A number of approaches have been taken by researchers. Implicitly or explic-itly, most of them are based on mathematical constructs known as kinematic chains,1From discussions with Al Vaisius.1Chapter 1. Introduction(a) (b) (c)Figure 1.1: a) Fragment of mouse mammary tumour virus mRNA that causes aframe shift conformation in the mRNA , (b) yeast tRNA, and (c) a regulatory RNAtranscribed from the human immunodeficiency virus, HIV, pro-viral DNA. Imagesfrom [Dat16], NDB IDs are 1RNK, TRNA03, and 1ANR, respectively.models of rigid objects that dominate the field of robotics[Ang07]. Chemical bondsand angles are treated as fixed instead of the semi-flexible objects they are and themachinery of kinematic chains is used to generate descriptions of RNA’s confor-mation space, or full range of possible bendings and twistings. 푓 (Equation 1.1)becomes a description of the chain, usually represented as a product of transforma-tion matrices.In the case of individual backbones, [Mak08] developed a numerical techniquefor finding the pre-image 푓−1 for individual points in the conformation space (i.e.specific conformations), later generalizing it to multiple backbones using MonteCarlo methods [MCM11]. Similar results were produced by [PRT+07] for generalchemical structures, though at the cost of computational speed. [KHP11] took theapproach of reducing the dimensionality of the problem by replacing the six back-bone torsion angles with two. Although the reduction supposedly captures the bulkof information for multi-nucleotide backbones, its nevertheless discards consider-able available data. In a different vein, kinematic chains are used in [WKM+08]to correct steric clashes, the energetically-unfavourable collision of atoms resultingfrom certain conformations, in existing crystallographic data. There is at least onecase where 푓−1 has been solved analytically, although in the context of proteins and2Chapter 1. Introduction(a) (b)Figure 1.2: Dinucleotide strands of (a) DNA and (b) RNA, both consisting of thesame two nucleosides, cytosine and adenosine (colored boxes), the structures ofwhich are not shown. The structure of the phosphate backbone, which for a singlenucleotide consists of the atoms between successive phosphate atoms, inclusively,is the same for both DNA and RNA. The key difference between the two moleculesis the presence of a hydroxyl group (OH) in the sugar ring of RNA. Figures from[LNC93].3Chapter 1. Introductionat the expense of idealizing bond angle values [MLL08]2.By defining a phosphate backbone as a special kind of redundant kinematicchain, the problem of solving the entirety of 푓−1 is theoretically possible using thetechnique of [PRT+07]. Indeed, this approach was originally pursued by myself,however the process was both inelegant and impractical: it more than double thenumber of variables by introducing seven new degrees of freedom3.The primary limitation of previous attempts to solve the RNA conformationproblem is the very assumption which allowed them to use kinematic chains inthe first place - that phosphate backbones are rigid objects. Chemical bonds areinherently flexible, undergoing compression and extension, while the mathematicsmodelling them is strictly rigid. The conformation problem for RNA can thus beconsidered as a special case of a more general problem in the theory of kinematicchains, namely how to incorporate semi-rigid objects in a rigid mathematics. It isthe general problem that this work seeks to address, with its development conductedthrough the lens of RNA to provide a concrete example.The main aim of this work, technically stated, is to approximate subsets of theconformation space of arbitrary kinematic chains which provide finite inverse kine-matic (IK) solutions, or finite values for 푓−1 in Equation 1.1. Infinite solutionsare treated as boundaries between these finite regions. The semi-rigidity of chaincomponents is accounted for by repeated approximations of the range of each com-ponent’s flexibility, then averaging them to form a new approximation.While the technique applies, in theory, to the finite components of any type ofkinematic chain, we’ll be restricting our analysis almost exclusively to 6푅 chains,the kinematic equivalent of a linear molecule consisting of six sigma bonds, ofwhich the phosphate backbone is one. In addition, the technique is predicated onthe existence of high-speed algorithms, specifically, those that can quickly solveIK solutions. Fortunately, such algorithms exist for 6푅 chains [MC94] in generaland phosphate backbones specifically [Mak08]. Should these algorithms ultimatelyprove too slow, however, or should they not exist for certain other types of chains,then the technique is not without merit - it simply anticipates the products of futureresearch.Two related sub-problems concerning RNA are also addressed. The first in-volves identifying stable conformations, or the set of energetically favourable statesof a backbone, while the second involves identifying likely pathways between anytwo conformations. Conformational pathways, the continuous sequence of bend-ings and twistings that RNA takes to move from one conformation to another, haveimportant applications in the field of pharmaceutical development. RNA-based2A sequence of three amino acids has an associated kinematic chain similar to that of RNA.3The process involved incorporating two spherical and one prismatic kinematic pairs.4Chapter 1. Introduction(a) (b)Figure 1.3: (a) A portion of HIV-1 TAR RNA in an inactive state, prior to bindingto another biomolecule, and (b) the same, nearly identical portion in HIV-2 in anactive state post-binding. Although the two structures are from different strains ofHIV, the binding properties are similar [BW97]. Images from [Dat16], NDB IDsare 1ANR and 1AJU, respectively.5Chapter 1. Introductionbased diseases can be at least partially driven by conformational changes in RNA4.In the case of HIV, there exist two conformations for an important trans-activatorregulating RNA, TAR, that is involved in the kinetics of HIV provirus transcriptionand resultant infectivity (Figure 1.3) [BW97]. Should the conformational path-way(s) between the two states be identified, it may be possible to design drugs thatspecifically target regions of the viral RNA that block the pathway(s), effectivelyinactivating it.There are three research goals to this work:1. Generate approximations for the finite inverse kinematic components of ar-bitrary kinematic chains, with specific focus on individual RNA phosphatebackbones, that account for semi-flexible components;2. Identify energetically favourable conformations for individual backbones;3. Identify energetically favourable pathways between conformations for indi-vidual backbones.In order to address these goals, it was necessary to construct novel graph-likestructures called stacked graphs. Chapters 2 through 4 are dedicated to introducingthese structures. Chapter 2 defines stacked graphs and the basics of their mathemat-ics, including the notion of feasible assignments, or ‘solutions’ to stacked graphsthat, in our case, approximate conformation spaces. The chapter culminates in The-orem 2.31, which provides necessary and sufficient conditions for assignment fea-sibility. Chapter 3 explores the close relationship between stacked graphs and thesymmetric groups. While the chapter is not required to solve the conformationproblem, it does provide a succinct notation for modelling it, as well as being asubject worthy of discussion in and of itself. Chapter 4 constructs a linear programfor finding minimally weighted feasible assignments, or optimal approximations toa conformation space that satisfy the conditions of Theorem 2.31.Chapters 5 through 8 focus on the techniques and mathematics required to writethe phosphate backbone conformation space problem in terms of stacked graphs.Chapter 5 reviews the theory of kinematic chains to a level sufficient to understandthe conformation space problem. Chapter 6 describes the methodology for sam-pling a conformation space, in addition to formally defining the conformation prob-lem. These samples form a data set from which, in Chapter 7, a stacked graph willbe constructed. The optimal feasible assignment to this stacked graph is shown tobe an approximation to the conformation space problem for rigid kinematic chains.In Chapter 8 we define a number of metrics for determining the accuracy of our ap-proximations. In addition, we locate stable conformations for individual phosphate4From discussions with Al Vasius.6Chapter 1. Introductionbackbones as well as likely conformational pathways by converting stacked graphsinto Markov chains. Finally, a new kind of ‘averaged’ stacked graph is defined toaccount for semi-flexible kinematic chains. Chapter 9 reviews the work and detailsprimary topics that need to be addressed by future research.As far as I am aware, the theory of stacked graphs is original to this work. I havebeen unable to find an equivalent to it in existing literature, although a previousdiscovery is certainly possible.7Chapter 2Stacked GraphsThis chapter introduces stacked graphs. The first section provides a non-technicalexample of what is meant by ‘approximating a conformation space’ using a pairof curves, while presenting stacked graphs in an intuitive manner. Only a limitedmathematical background is assumed in this section. The remaining portions of thechapter formally construct the mathematics of stacked graphs.2.1 Motivating ExampleSuppose we have a mapping 푓 between two metric spaces5푓 ∶ 푋 → 푌 (2.1)where 푓 is neither one-to-one nor onto6. We’ll further suppose that we cannotfind 푓 (푋) explicitly, although we know that 푓 (푋) consists of a finite number ofconnected components. We have, however, a subset 푆 of 푋 where 푓 (푥푖) is knownfor all 푥푖 ∈ 푆, and where each 푓 (푥푖) consists of a finite number of elements in 푌푓 (푥푖) = {푦푖푗|푗 = 0, 1, 2,…푚, ∀푥푖 ∈ 푆푛}. (2.2)Perhaps 푓 is a real world function describing natural phenomenon we wish to un-derstand and each 푓 (푥푖) is an experimental sample. Or, perhaps 푓 is an inverseimage of a function and each 푓 (푥푖) is a numerical approximation. In either case,we would like to know whether we can use the elements 푆 to approximate the en-tirety of 푓 (푋). The following example suggests that this is possible in some cases.Let 푓 (푋) be the stretched annulus of Figure 2.1(a), although we don’t know itis. We’ll take our sample point-set 푆 in 푋 to be푆 ∶= {푥푖|푥푖 < 푥푖+1, 푖 = 0, 1,… , 12, 푥푖 ∈ 푋}. (2.3)By looking at Figure 2.1(a), the following two properties for are intuitively true if|푆| is sufficiently large and 푆 provides good coverage of 푋. First, (almost) every5Spaces that have a notion of ‘distance’.6A single point in푋 may map to many points in 푌 , but not ever point in 푌 can be arrived at froma point in 푋.82.1. Motivating Exampletwo successive values 푥푖 and 푥푖+1 will have images 푓 (푥푖) and 푓 (푥푖+1), respectively,of equal size |푓 (푥푖)| = |푓 (푥푖+1)|. (2.4)Second, for (almost) every successive pair 푥푖 and 푥푖+1, for every value 푦푖푗 in 푓 (푥푖)there is exactly one ‘special’ value 푦푖+1푘 in 푓 (푥푖+1) such that, as the distance between푥푖 and 푥푖+1 approaches zero, the distance between these special pairs of values alsoapproaches zero. Technically stated,|푓 (푥푖) − 푓 (푥푖+1)|→ ∞ ⟹ ∀푦푖푗 ∈ 푓 (푥푖) ∃! 푦푖+1푘 ∈ 푓 (푥푖+1) ∋ |푦푖푗 − 푦푖+1푘 | → 0.(2.5)Figure 2.1 illustrates both properties. The ‘almost’ qualifier exists as there are caseswhere these conditions do not hold (i.e. 푓 (푥3) and 푓 (푥4)). However, the numberof cases is finite. The properties as they related to the conformation space problemare discussed in detail in Chapter 7. At present, we’ll take them as given.While we know that there exist pairs of values, one each from 푓 (푥푖) and 푓 (푥푖+1),that approach each other in the limit, we don’t know which pair. We only know thatsuch pairs exist. As a result, we must consider every possible approach betweensuccessive image sets (Figure 2.2).To this end, we view each image set as a ‘stack’ of vertices and the set of possibleapproaches between each successive image pair 푓 (푥푖) and 푓 (푥푖+1) as a ‘stack’ ofedges. These vertex and edge stacks form a succession of complete bipartite graphs(Figure 2.3(a)). Let 푉푖 be the vertex associate with 푓 (푥푖) and 퐸푖(푖+1) be the edgestack between 푉푖 and 푉푖+1. When |푓푥푖| = |푓 (푥푖+1)|, an approach ‘solution’ is aperfect matching or set of disjoint edges [Fou92] mapping each vertex in 푉푖 to aunique vertex in 푉푖+1. There are many possible matchings, or ‘assignments’.One possible‘assignment for our sample set 푆 is show in bold line in Figure2.3(b). The assignment gives a reasonable approximation of 푓 (푋), though thereis an obvious error in the lower portion between 푉6 and푉7. There is also the issueof what to make of edge stacks whose vertex stacks are of different sizes, whichresults when |푓푥푖| ≠ |푓 (푥푖+1)|, such as between 푉3 and 푉4, and 푉10 and 푉11. These‘singularities’ add a layer of complication that cannot be address in this preliminarysection.Determining the best set of approaches for an edge stack is related to the classicweighted bipartite matching, or assignment, problem [AMO93], and involves linearoptimization. If 푆 is large enough and covers 푋, then the optimal] assignment on푆 forms a piece-wise linear approximation of 푓 (푋). For our choice of 푆 above thebest approximation of 푓 (푋) is that of Figure 2.4.The above annulus example is a mathematical introduction to the primary aimof this work. Instead of an annulus, the mapping 푓 we wish to approximate, which92.1. Motivating Example(a)(b)Figure 2.1: (a) The annulus 푓 (푋)with awell-distributed collection of sample points푥푖. Note that 푓 (푥0) is empty. Most 푥푖 have the same number of image values 푓 (푥푖)as 푥푖+1. (b) In each of these cases, one value in 푓 (푥푖) is on the same portion of theannulus as exactly one value in 푓 (푥푖+1), so that, if 푥푖 and 푥푖+1 were to approacheach other, the two corresponding values in 푓 (푥푖) and 푓 (푥푖+1) would do likewise,as with 푓 (푥5) and 푓 (푥6).102.1. Motivating Example(a) (b)Figure 2.2: (a) As 푓 (푋) is unknown, its possible that 푦52 approaches any one of 푦60,푦61, 푦62, and 푦63. (b) We must therefore assume all possible approaches.corresponds to the phosphate backbone conformation space, is actually the inverseimage of a six-dimensional manifold. The limit behaviour as 푓 (푥푖) approaches푓 (푥푖+1) is expressed as shrinking neighbourhoods of open sets, while the singulari-ties produced when |푓 (푥푖)| ≠ |푓 (푥푖+1)| result, in part, when there is an intervening푥푘 ∈ 푋푥푖 < 푥푘 < 푥푖+1 (2.6)where |푓 (푥푘)| is uncountable. The rest of this chapter is dedicated to developing themathematics of stacked graphs necessary for our project. The optimization compo-nent for finding minimally weighted assignments is the subject of Chapter 4. Theintervening Chapter 3 develops amethod of writing stacked graphs, which are rathercomplicated, in simple algebraic terms. That the approximation in Figure 2.4 doesnot produce the disjoint components of 푓 (푋) is a consequence of how singularitiesare handled. It’s possible, however, to interpolate disjointedness in certain cases.This is covered briefly in Section Motivating Example(a)(b)Figure 2.3: (a) The conversion of each 푓 (푥푖) to vertex stack 푉푖 produces a completebipartite graph between every successive pair 푉푖 and 푉푖+1. (b) Creating an assign-ment (bold), or set of approach solutions, for every edge stack 퐸푖(푖+1), or bipartitegraph, produces a linear approximation to 푓 (푋) (dashed).122.2. Constructing Stacked GraphsFigure 2.4: An optimal linear approximation to 푓 (푋) based on 푆.2.2 Constructing Stacked GraphsStacked graphs are a class of graphs formed by replacing each vertex with a setof indexed vertices and each edge with a complete bipartite graph between adjacentvertex stacks.Definition 2.1 (Stacked Graphs). A vertex stack is an indexed set of vertices푉푘 ∶= {푣푘푖 |푖 = 0, 1,… , 푚}. (2.7)The size of a vertex stack is |푉푘|. An edge stack is the complete bipartite graphformed between the vertices of two vertex stacks, 푉푝 and 푉푞7퐸푝푞 ∶= {푒푝푞푖푗 |푖 = 0, 1,… , |푉푝| − 1; 푗 = 0, 1,… , |푉푞| − 1}. (2.8)Let = {푉푘 | 푘 = 0, 1,…} be a set of vertex stacks and  = {퐸푝푞 | 푉푝, 푉푞 ∈ }be a set of edge stacks formed on  . Then 픾 = ( , ) is a stacked graph.If 퐸푝푞 ∈ 픾, then 푉푝 and 푉푞 are adjacent. If |푉푝| = |푉푞|, then the 퐸푝푞 is asin-gular. Otherwise, it’s singular. The size of an asingular 퐸푝푞, denoted by |퐸푝푞|, is|푉푝|. If 퐸푝푞 is singular and |푉푝| > |푉푞|, then 푉푝 is the collapsing vertex stack and푉푞 is the expanding vertex stack of 퐸푝푞.7A complete bipartite graph consists of two sets of vertices 푉푎 and 푉푏 where every vertex in 푉푎 isadjacent to every vertex in 푉푏, but no edge exists between vertices within 푉푎 or 푉푏 [Bol79].132.2. Constructing Stacked GraphsIf 픾 is composed entirely of singular edge stacks, then 픾 is singular. The sameapplies in the asingular case. If 픾 is neither singular nor asingular, it’s mixed. If 픾is asingular and connected, then the size of 픾, |픾|, is |퐸푝푞| for some 퐸푝푞 ∈ 픾8.Examples of singular and asingular edge stacks are shown in Figure 2.5.Figure 2.5: Adjacent stacks 푉푝 and 푉푞 form an asingular stack 퐸푝푞 since |푉푝| =|푉푞| = 4. However, 퐸푝′푞′ is singular as |푉푝′| = 2 and |푉푞′| = 3.Stacked graphs maintain all the properties of ‘unstacked’ graphs: every graphconcept has an analogous stacked version.Definition 2.2 (Stacked Analogues). A stacked analogue is a graph structure inwhich every vertex stack 푉푘 or edge stack 퐸푝푞 is viewed as a single vertex 푣푘 oredge 푒푝푞.For example, a path stack is a path composed of vertex and edge stacks푉푖 − 퐸푖푗 − 푉푗 − 퐸푗푘 − 푉푘 −…or퐸푖푗 − 퐸푗푘 −… .The naming convention for stacked analogues is to either postfix a term withthe word ‘stack’, or prefix it with ‘stacked’. Both are legitimate.98It’s possible that an asingular disconnected 픾 contains vertex stacks of different sizes, as isolatedvertex stacks of different sizes can exist in asingular 픾.9With the exception of stacked graphs - such as a stacked lattice graph - preference is given tousing ‘stack’ over ‘stacked’. Saying ‘stacked path’ and ‘stacked cycle’ is rather awkward.142.2. Constructing Stacked GraphsAswith stacked graphs in general, stacked analogues take one of three followingforms, depending on the nature of the constituent edge stacks: singular, asingular,ormixed. If an analogue is asingular, its size is the size of its constituent edge stacks.Due to their ubiquity, it will help to have a succinct notation for path and cyclestacks.Definition 2.3 (Path and Cycle Stacks). A path stack of length 푛 is 푛. If it’sasingular size 푚, then its denoted by 푛푚. Cycle stacks are similarly defined for 푛and 푛푚.It may at times be helpful to view stacked graphs as unstacked graphs, and viceversa.Definition 2.4 (Un/Packing Graphs). If a stacked graph픾 is viewed as an unstackedgraph, that is, as a collection of vertices and edges, not vertex and edge stacks, then픾 is denoted by 픾, read as 픾 unpacked as .Likewise, if ′ is graph isomorphic to some 픾, then ′ can be viewed as thestacked graph, 픾, read  packed as 픾.Packing and unpacking can be restricted to paths, cycles, and their stacked ana-logues, such as 푛푚 and 푛푚 .The process of unpacking a stacked graph exposes the edges and nodes, whilepackaging an unstacked graph hides them. We mention packings only in passing asthey’re not necessary for this work. In general, packings are not unique and every has at least one trivial packaging, formed by assigning to each vertex in  a vertexstack of size one. Figure 2.6 gives an example of different packings for a smallgraph.Given any graph , it’s possible to generate an asingular stacked graph 픾 withthe same underlying structure, and vice versa.Definition 2.5 (Graph Collapse and Expansion). The 푚th expansion of , ̂푚, is theasingular stacked graph formed by replacing all vertices and edges in  with vertexand edge stacks of size 푚.Likewise, if 픾 is singular, asingular, or mixed, then the collapse of 픾, 픾̌, is thegraph formed by replacing each vertex and edge stack in 픾 with a single vertex andedge, respectively.As with un/packings, collapses and expansions can be restricted to structures152.2. Constructing Stacked Graphs(a) (b) (c)(d) (e)Figure 2.6: (a) An unstacked graph  and five packings 픾: (b) the trivial packingand packings producing (c) four, (d) three, and (e) two vertex stacks. Vertices ofthe same color are part of the same stack.162.2. Constructing Stacked Graphssuch as paths (stacks) and cycles (stacks)10̌푛푚 → 푃 푛푃̂ 푛푚 → 푛푚̌푛푚 → 퐶푛퐶̂푛푚 → 푛푚Expansions, collapses, and unpacking introduce five of ways of modifying orviewing the graphical structures  and 픾: ̂푚, ̂푚 , 픾, 픾̌, and 픾̌.Lemma 2.6. Every unstacked graph  can be treated as a stacked graph of size 1by taking the first expansion, ̂1. The processes can be reversed by unpacking ̂1.That is  = ̂1.Unpacking is thus the inverse function of the first expansion.Proof. The proof is obvious.First expansions ̂1 provide a sort of ‘wrapper’ function for unstacked graphs,allowing us to treat them as being stacked. Analogues, on the other hand, let ustreat stacked graphs as ‘graph-like’ objects in their own right: path stack connec-tivity is identical to path connectivity - except with path stacks. To limit confusion,however, we need to keep track of the words ‘stack’ and ‘stacked’. Unless they’reexplicitly used, it’s assumed that we’re dealingwith unstacked structures/properties.Drawing stacked graphs is difficult. Explicitly displaying edges 푒푝푞푖푗 of some 픾while making the underlying structure of 픾 obvious leads to extremely crowdeddiagram. This is true in even the simplest cases where 픾 consists of few edgestacks, all of which are asingular and of small size. To facilitate ease of reading,two different graphical notations are used, depending on the needs at hand.Definition 2.7 (Packed and Upacked Diagrams). For any stacked graph 픾, the un-packed diagram of 픾 show the vertices and edges of each constituent vertex andedge stack, while the packed diagram shows only the vertex and edge stacks.Figure 2.7 illustrates the difference between packed an unpacked diagrams.When large unpacked stacked graphs are used, the vertex labels will often be sup-pressed and vertices will be coloured instead, as in Figures 2.6 and 2.18.Singular and asingular edge stacks are wildly different creatures. In the case ofmixed 픾, being able to work with its singular and asingular components separatelywill prove useful.10This is one reason why consistent usage of style is important: 푃̂ 푛푚 and 푛푚 have two differentmeanings, even if though the former produces the latter.172.2. Constructing Stacked Graphs(a) (b)Figure 2.7: The (a) unpacked and (b) packed diagrams of 32.Definition 2.8 (De/Singularization of 픾). Let the set of singular edge stacks ofany 픾 be ̉ . Then 픾̐ is the desingularization of 픾, or the asingular stacked graphinduced by 픾픾̐ ∶= ( ,  − ̉). (2.9)Similarly, 픾̉ 11 is the singularization of픾, or the singular stacked graph inducedby 픾픾̉ ∶= ( , ̉). (2.10)Fact 2.9. If 픾 is asingular, than 픾̐ = 픾 and 픾̉ has no edge stacks. If 픾 is singular,then 픾̉ = 픾 and 픾̐ has no edge stack.The connected component stacks of 픾̐ and the edge stacks of 픾̉ are special.Definition 2.10 (Regions). The set of connected component stacks of 픾̐, 픾, arethe regions of 픾픾 ∶= {푖 | 푖 = 0, 1,…}. (2.11)All vertex stacks 푉푘 ∈ 푖 are of the same size12, which is also the size of푖, |푖|.Definition 2.11 (Regional Boundaries). If 푟 and 푡 are two regions of 픾 suchthat |푟| ≠ |푡|, with 푉푝 ∈ 푟, 푉푞 ∈ 푡 and 퐸푝푞 ∈ 픾, then 퐸푝푞 ∈ 픾̉. The setof all such edge stacks for 푟 and 푡 is the (singular) boundary between 푟 and푡, denoted by ̉푟푡. If |푟| > |푡|, then 푟 is the collapsing region and 푡 is theexpanding region.11Concerning the accents used, ̐ resembles two disjoint regions, while ̉ resembles the negativespace of ̐ .12This is easily derivable and need not be part of the definition.182.3. Assignments and FeasibilityIf ̉푟푡 is non-empty, then 푟 and 푡 are adjacent, otherwise they are not adja-cent.Regions are connected component stacks, not components. If 픾 is singular,then 픾̐ has no edges and every node is disconnected. 픾̐ would thus have a largenumber of components, but 픾̐ would have only || component stacks, or regions.Asingular cycle stacks are a core feature of stacked graphs and will be used to formthe stacked analogue of a cycle basis.Definition 2.12 (Fringe and Core of픾). Let퐸푝푞 be any asingular edge stack in픾. If퐸푝푞 belongs to an asingular cycle stack, then 퐸푝푞 is a cyclic edge stack. Otherwise퐸푝푞 is an acyclic edge stack.The stacked sub-graph of 픾 composed of all acyclic edges stacks of 픾 is thefringe 픾̃ of 픾, while the stacked sub-graph composed of all cyclic edge stacks is thecore of 픾̊13.Fact 2.13. 픾̃ is a tree or forest.Fact 2.13 follows immediately from the definition of 픾̃.Lemma 2.14 (Fringe, Core, and Singular Edges of 픾). For any 픾, the three sub-graph stacks 픾̃, 픾̊, and 픾̉ partition the edge stacks  of 픾 into disjoint sets.Proof. Every edge stack is singular, asingular and part of a cycle stack, or asingularand not part of a cycle stacks.Thus there exists an equivalence relation on  of 픾 with three classes definedby 픾̃, 픾̊, and 픾̉.2.3 Assignments and FeasibilityAssignments are essentially special kinds of network flow solutions to 픾.Definition 2.15 (Edge Stack Assignment). An assignment 퐴 on 퐸푝푞퐴푝푞 ∶= 퐴(퐸푝푞)is an onto mapping from the collapsing vertex stack of 퐸푝푞 to the expanding one.If 퐸푝푞 is asingular, then the mapping is one-to-one and onto.13Concerning the accents used, ̊ resembles a cycle while ̃ resembles a path.192.3. Assignments and Feasibility(a) (b) (c) (d) (e)Figure 2.8: Asingular edge stacks assignments (bold lines) that are (a) valid and(b) invalid. For singular edge stacks, the number of assignment edges is equal tothe largest size of the two vertex stacks. A (c) valid assignment ensures that everyvertex in one stack is adjacent to at least one vertex in the other while (d) invalidsingular assignments may have insufficient edges and/or (e) incomplete adjacency.The flow value14 of 푒푝푞푖푗 under 퐴푝푞 is denoted by 푥푝푞푖푗 . Unless otherwise stated,flow values are binary푥푝푞푖푗 ∈ {0, 1}. (2.12)If 퐴푝푞 maps 푣푝푖 to 푣푞푗 , then 푥푝푞푖푗 = 1 and 푥푝푞푖푗 = 0 otherwise.Let |푉푝| ≥ |푉푞|. The 푖th edge flow of 퐴푝푞, denoted by 푥푝푞푖 , corresponds to theedge incident on 푣푝푖 whose flow value is non-zero15.Figure 2.8 gives an example of valid and invalid assignments for both singularand asingular edge stacks.Definition 2.16 (Stacked Graph Assignment). An assignment 퐴 on 픾, 퐴(픾), pro-vides an assignment 퐴푝푞 for every 퐸푝푞 ∈ 픾.If ℍ is a sub-stacked graph of 픾 and 퐴 an assignment on 픾, then 퐴(ℍ) is therestriction of 퐴 to ℍ.We’ll often treat assignments as unstacked graphs in their own right. Whenreferring to ‘an edge of 퐴푝푞’, we actually mean an edge in 퐴(퐸푝푞) with non-zeroflow. This allows us to write things like푒푝푞푖푗 ∈ 퐴푝푞 (2.13)14Flow values form solutions to network flow problems [AMO93].15By the definition of an assignment, such an edge always exist and exists.202.3. Assignments and Feasibilitywhich, though technically incorrect, provides a useful shorthand. Diagramatically,assignments will always be indicated as bold edges.Assignments on 퐸푝푞 are related to the classic assignment problems on bipartitegraphs [AMO93]. Similarly, assignments on 픾 can be thought of as solutions to acollection of inter-related assignment problems.Not all assignments are created equal, however.Definition 2.17 (Assignment Feasibility). Let 퐴 be an assignment on 픾. Then퐴(픾) is feasible if, for every 푉푝 ∈ 픾, the vertices of 푉푝 are path disjoint in 퐴(픾̐).Otherwise, 퐴(픾) is infeasible.Equivalently, 퐴(픾) is feasible if, for any path connected vertices 푣푝푖 and 푣푝푗 in퐴(픾), every path connecting them contains at least one edge belonging to a singularedge stack.The remainder of this section is dedicated to proving necessary and sufficientconditions for assignment feasibility, culminating in Theorems 2.31 and 2.32. Theprocess begins by looking at the application of assignments to path stacks.Theorem 2.18 (Paths of a Path Stack). For any assignment퐴 on an asingular pathstack 푛푚, 퐴(푛푚) consists of exactly 푚 disjoint paths of length 푛. If 푛푚 begins at푉푎 and ends at 푉푏, then each path of length 푛 in 퐴(푛푚) begins at a vertex 푣푎푖 andends at a vertex 푣푏푗 . Furthermore, the maximum length of a path in 퐴(푛푚) is 푛.Proof. By definition, for each 퐸푝푞 in 푛푚, 퐴푝푞 consists of 푚 disjoint edges, orpaths of length 1. For any adjacent pair 퐸푝푞 and 퐸푞푟 in 푛푚, every edge 푒푝푞푖푗 ∈ 퐴푝푞is adjacent to exactly one edge 푒푞푟푗푘. Thus an assignment on any path stack of length2퐸푝푞 − 퐸푞푟consists of 푚 disjoint paths of length 2. By induction on the length of 푛푚, 퐴(푛푚)consists of 푚 disjoint paths of length 푛.Two corollaries follow from Theorem 2.18.Corollary 2.19. All assignments 퐴 on any asingular 푛푚 are feasible.Proof. The proof follows from that of Theorem 2.18 by induction on 푛 and 푚.Corollary 2.20. The disjoint paths 푃푖 of 퐴(푛푚) for any 퐴 are isomorphic to 푛푚and form a disjoint vertex cover of 푛푚 .Proof. By definition of an assignment on asingular edge stacks, every 푣푝푖 ∈ 푉푝maps to exactly one 푣푞푗 ∈ 푉푞. Thus 푒푝푞푖푗 is isomorphic to 퐸푝푞 and each vertex in 푉푝and 푉푞 is covered by some edge in퐴푝푞. By induction on the edge stacks, every path푃푖 ∈ 퐴(푛푚) is isomorphic to 푛푚 and form a covering of the vertices in 푛푚 .212.3. Assignments and FeasibilityFigure 2.9 gives an example of a feasible assignment on 44. From it, it’s easyto visualize the proof of Corollary 2.20.Figure 2.9: Any assignment 퐴 on a path stack 44 will create 4 paths of length 4.We now turn tomaintaining assignment feasibility onmore complicated graphs,starting with cycle stacks.Consider an asingular, 3-cycle stack, 32, formed by 푉0, 푉1, and 푉2. Assign-ment 퐴0(32) (Figure 2.10(a)) is infeasible as 푣00 and 푣01 are path connected by푣00 − 푣10 − 푣21 − 푣01. (2.14)In fact, all vertices are path connected since 퐴0(32) describes a vertex cycle coverconsisting of a single cycle. 퐴1(32), however, is feasible (Fig 2.10(b)). The twoconnected components of퐴1(퐶32) each contain exactly one vertex from each vertexstack.퐴1(32) suggests a necessary condition for assignment feasibility of cycle stacks.Lemma 2.21. If 퐴 is a feasible assignment on asingular 푛푚, then 퐴(푛푚) forms adisjoint cycle cover of the vertices of 푛푚 .Proof. The proof relies on the asingular nature of 푛푚. It follows from the definitionof edge stack assignments (Definition 2.15) that, for any two adjacent edge stacks퐸푝푞 and 퐸푞푤 in 푛푚, every 푣푞푗 is adjacent on exactly two other vertices 푣푝푖 and 푣푤푘in 퐴(푛푚). This implies that every vertex belongs to a cycle16. By assumption,퐴(푛푚) is feasible, so that intra-vertex stack vertices are path disconnected. Thus,all vertices in a given vertex stack belong to disjoint cycles. 퐴(푛푚) is therefore adisjoint cycle cover of the vertices of 푛푚 .16If they did not, then they would necessarily belong to a path. However, paths of non-zero lengthconsist of at least two vertices incident on only a single edge.222.3. Assignments and Feasibility(a) (b)Figure 2.10: (a) 퐴0(32) does not enforce path disjointedness of intra-stack nodeswhile (b) 퐴1(32) does.The converse is not true. Figure 2.11 gives an example of a disjoint cycle coveron 42 which is neither feasible nor an assignment.Figure 2.11: A disjoint cycle cover of 42 that does not form a feasible assignment.Lemma 2.22. If 퐴 is feasible on some 푛푚, then there are 푚 disjoint cycles in퐴(푛푚), each of length 푛.Proof. By definition of a cycle, a cycle stack is a path stack that starts and endson the same vertex stack 푉푘. Viewed as a path stack, by Theorem 2.18 there exist푚 disjoint paths of length 푛 in 퐴(푛푚), each starting and ending in 푉푘. However,232.3. Assignments and Feasibilitysince 퐴(푛푚) is feasible, it is necessarily the case that each path starts and ends onthe same vertex in 푉푘 in order to prevent path connectedness between the nodes of푉푘. Thus, each path is a cycle and disjoint. Therefore, there are 푚 disjoint cyclesof length 푛 in 퐴(푛푚).Theorem 2.22 leads to a key theorem about asingular cycle stacks and theirfeasible assignments.Theorem 2.23 (Disjoint Cycles of Feasible Asingular Cycle Stack Assignments).Let 퐴 be an assignment on asingular 푛푚. Then, 퐴(푛푚) is feasible if and only if itforms a disjoint cycle cover of the vertices of 푛푚 , consisting of 푚 cycles, each oflength 푛.17Proof. For the forward portion, see proofs for Lemmas 2.21 and 2.22. The proof forthe backwards portion, that an assignment which produces an appropriate disjointcycle cover is necessarily feasible, is as follows.Let  (푛−1)푚 be the asingular path stack (푛−1)푚 ∶= 퐸01 − 퐸12 −⋯ − 퐸(푛−2)(푛−1) (2.15)and let 퐴 be some assignment on it. Introduce a new edge stack 퐸(푛−1)0 and appendit to  (푛−1)푚 to create the asingular cycle stack 푛푚 (Figure 2.12). In addition,introduce an assignment 퐴(푛−1)0 onto 퐸(푛−1)0.Let 퐴(푛푚) be the extension of 퐴 applied to  (푛−1)푚 by incorporating 퐴(푛−1)0.In other words, 퐴( (푛−1)푚) is the proper sub-graph of 퐴(푛푚) formed by removingthe edges of 퐴(푛−1)0. By Corollary 2.19, 퐴( (푛−1)푚) is feasible, meaning that thefeasibility of 퐴(푛푚) is dependent on 퐴(푛−1)0.From Theorem 2.18 we know that 퐴( (푛−1)푚) consists of 푚 disjoint paths oflength 푛 − 1. Without loss of generality, choose path 푃푖. Let 푣0푎 and 푣푛−1푏 for some푎, 푏 ∈ {0, 1,… , (푚−1)} be the first and last nodes of 푃푖, respectively. By Definition2.15, 푣푛−1푏 is adjacent to exactly one vertex in 푉0. If 푣푛−1푏 is not adjacent to 푣0푎, itforms a path with a length of at least 2푛 − 1 (Figure 2.13(a)) and includes twovertices in 푉0, violating the assumption of independence. Thus 푣푛−1푏 is adjacent to푣0푎, which forms a cycle 퐶푖 of length 푛 containing only a single vertex from eachvertex stack (Figure 2.13(b)).As each cycle 퐶푖 contains exactly one vertex from each vertex stack, and aseach vertex stack is of size 푚, it follows that there are 푚 disjoint cycles of length 푛.Therefore, if 퐴(푛푚) is a disjoint cycle cover of the vertices of 푛푚 consistingof 푚 cycles of length 푛, 퐴(푛푚) is feasible.17We’re assuming the disjoint cover cycle is produced by an assignment. We know there existdisjoint cover cycles for some 푛푚 consisting of 푚 cycles of length 푛 that do not form assignments(Figure 2.11).242.3. Assignments and FeasibilityFigure 2.12:  (푛−1)푚 extended to 푛푚 by the inclusion of 퐸(푛−1)0, with 푚 = 2.There are two special cases for assignment feasibility on 푛푚, namely when푛 = 1 and 푛 = 2. These are addressed in Section 2.4.Corollary 2.24. If퐴 is a feasible assignment on any asingular 푛푚, then the disjointcycles 퐶푖 of 퐴(푛푚) are isomorphic to 푛푚.Proof. See proof for Corollary 2.20.Theorem 2.23 provides necessary and sufficient conditions for assignment fea-sibility on arbitrary asingular cycle stacks. This leads immediately to necessary andsufficient conditions for assignment feasibility on any asingular 픾.Theorem 2.25 (Feasibility of 픾). For any assignment 퐴 on 픾, 퐴(픾) is feasible ifand only if, for every asingular cycle stack 푛푚 in 픾, 퐴(푛푚) is feasible.Proof. For the forward component, 퐴(푛푚) is a sub-graph of 퐴(픾), so that any twovertices 푣푝푖 and 푣푞푗 that are path disconnected in 퐴(픾) are necessarily so in 퐴(푛푚).For the backward component, every vertex stack belongs to a path and/or cyclestack. As feasibility is defined on asingular path and cycle stacks alone, we needonly consider vertex stacks in them. If 푉푖 is contained in one or more cycle stacks,then, by assumption, the vertices in 푉푖 are disjoint under 퐴. If 푉푖 is not in somecycle stack, then it is necessarily in one or more path stacks. By Corollary 2.19, all퐴(푛푚) are feasible, and by assumption, all 퐴(푛푚) are feasible. Therefore 퐴(픾) isfeasible.The conditions of Theorem 2.25 conditions are imposing: it requires that everyasingular cycle stack be checked for feasibility under퐴, which is tedious at best and252.3. Assignments and Feasibility(a) (b)Figure 2.13: Example of an assignment on  (푛−1)푚 and 푛푚, with 푚 = 2. If the endof path 푃푖 (blue) does not coincide with its start (red) via 퐸(푛−1)0, a path of length2푛−1 is formed (a). However, by assumption퐴(푛푚) is composed of disjoint cyclesof length 푛, implying that all paths are at most length 푛−1. It must be the case thenthat 푃푖 ends where it starts via 퐸(푛−1)0 to form a cycle (b).highly impractical in general. Fortunately, the conditions can be reduced to applysolely to the basis of a stacked graph’s cycle stacks.Lemma 2.26 (Feasibility of Joined Cycle Stacks). Let 픾 be asingular, of size 푚,and composed of two cycle stacks 푟푚 and 푡푚 which share a single common pathstack 푠푚 of length 푠 < min{푟, 푡} (Figure 2.14). In other words,푟푚 ∩퐸 푡푚 = 푠푚 (2.16)where ∩퐸 denotes the edge stacks shared between two stacked graph structures.Then assignment 퐴 on 픾 is feasible if and only if 퐴(푟푚) and 퐴(푡푚) are bothfeasible.Proof. The forward component is true by Theorem 2.25. For the backward com-ponent, the key is that 푠푚 is shared by both cycle stacks. By Theorem 2.18 andCorollary 2.19, 퐴(푠푚) creates 푚 disjoint paths 푃푘, irrespective of 퐴’s details. Inaddition, by Theorem 2.23, 퐴(푟푚) and 퐴(푡푚) each form 푚 disjoint cycles, 퐶푖 and퐶 ′푗 , respectively. Because 푠푚 is a stacked subgraph of by both cycle stacks, thesetwo properties imply that every disjoint cycle in 퐴(푟푚) shares a path of length푠 with exactly one disjoint cycle in 퐴(푡푚). Thus vertices disjoint in 퐴(푟푚) and퐴(푡푚) are also disjoint in 퐴(픾) (Figure 2.15).Therefore, if both 퐴(푟푚) and 퐴(푡푚) are feasible, 퐴(픾) is feasible.262.3. Assignments and FeasibilityFigure 2.14: Asingular 픾 formed by 푟푚 (blue and green) and 푡푚 (red and green)which share a single path 푠푚 (green).Lemma 2.26 can be generalized to two cycle stacks that share multiple disjointpaths.Lemma 2.27 (Feasibility of Multi-Joined Cycle Stacks). Let 픾 be as in Theorem2.26 except that 푡푚 and 푡푚 share multiple disjoint path stacks 푎푚, 푏푚, etc.(Figure 2.16). Then an assignment 퐴 on 픾 is feasible if and only if 퐴(푟푚) and퐴(푡푚) are feasible.Proof. The proof is the inductive application of the proof for Theorem 2.26 on eachshared path stack. Each path in 퐴(푎푚) is connected to one path in 퐴(푏푚), whichis connected to one path in 퐴(푐푚), etc., each of which is part of a single cycle in퐴(푟푚) and a single cycle in 퐴(푡푚).Lemma 2.26 also applies when 푠 = 0. In this case, 푟푚 and 푡푚 share only asingle vertex stack. This can be generalized to apply to any two disjoint cycle stackspath stack connected to each other.Lemma 2.28 (Feasibility of Path Stack Connected Cycle Stacks). Let 픾 be asin-gular, of size 푚, and composed of two edge stack disjoint cycle stacks 푟푚 and 푡푚which are path stack connected by 푠푚 such that푟푚 ∩퐸 푠푚 = ∅ (2.17)푡푚 ∩퐸 푠푚 = ∅, (2.18)where is ∩퐸 is as in Theorem 2.26 (Figure 2.17). Then an assignment 퐴 on 픾 isfeasible if and only if 퐴(푟푚) and 퐴(푡푚) are both feasible.272.3. Assignments and FeasibilityFigure 2.15: If every 퐶푖 and 퐶 ′푗 contain exactly one 푃푘 as a stacked subgraph, it’snecessarily the case that 푚 disjoint covers of 픾 are formed. In the case of 푚 = 2,for example, two covers can be formed by 퐶0 and 퐶 ′1 sharing 푃1, and 퐶1 and 퐶 ′0sharing 푃0.Proof. The proof is similar to that of Lemma 2.26 in that every disjoint cycle of퐴(푟푚) is connected to a single disjoint cycle in퐴(푡푚) via a single path in퐴(푠푚),and vice versa. Again, the details of 퐴(푠푚) are irrelevant.Lemmas 2.26 through 2.28 provide the components necessary to show that fea-sibility is preserved under the disjoint union of cycle stacks. The result is that, asa basis can always be found for the cycles of a graph - and consequently the cyclestacks of a stacked graph - and as cycles are formed via the disjoint union of basiscycles, then a feasible cycle stacks basis implies that all cycle stacks are feasible,and, consequently, an the entire assignment 퐴(픾).Theorem 2.29 (Feasibility of Cores). For asingular 픾 and assignment 퐴 on it,퐴(픾) is feasible if and only if 퐴(픾̊) is feasible.Proof. The proof is the same for Theorem 2.25.Corollary 2.30 (Feasibility of Fringes). For asingular 픾 and assignment 퐴 on it,퐴(픾̃) is always feasible.282.3. Assignments and FeasibilityFigure 2.16: 9푚 and 8푚 multi-joined by 1푚 and 2푚.Figure 2.17: Two edge stack disjoint cycle stacks 푟푚 and 푡푚 joined by 푠푚.Proof. By definition, 픾̃ contains only edge stacks that are not part of cycle stacksin 픾. Therefore, there are no cycle stacks in 픾̃. By Corollary 2.19 and Theorem2.25, 퐴(픾̃) is feasible.Recall that a spanning tree of a connected graph  is a connected sub-graphwhich covers the vertices of  and contains no cycles. The fundamental cyclesof a spanning tree are the cycles created by adding back the edges in  that wereremoved when creating the spanning tree [AMO93]. For any spanning tree of , theassociated fundamental cycles form a basis for the cycle space of  [Bol79]. Thatis, every cycle in  can be written as a disjoint union of some set of fundamentalcycles.This leads to the first cornerstone theorem of this work.Theorem 2.31 (Feasibility of Fundamental Cycle Stacks). Let 픾 = ( , ) be asin-gular and of size 푚, and let 핋 be a spanning tree stack of 픾. In addition, let292.3. Assignments and Feasibility핋 = {푖|푖 = 0, 1,… , 푘 − 1} be the set of fundamental cycle stacks associatedwith 핋 , where 푘 = ||− | |+1 18. Then any assignment 퐴 on 픾 is feasible if andonly if 퐴(푖) is feasible for all 푖 ∈ 핋 .Proof. The forward component is true by Theorem 2.25. For the backwards com-ponent, all cycle stacks of 핋 of are feasible. Any two fundamental cycles 푖 and푗 form one of three types: they are joined by one or more shared path stacks, orare disjoint but still path stack connected, or both. In the first case, Lemmas 2.26and 2.27 ensure feasibility is preserved, while Lemma 2.28 does the same for thesecond case. The third case is the combination of the first to, so that feasibilit ispreserved. Therefore, 퐴(픾) ia feasible.The restriction of Theorem 2.31 to asingular 픾 is merely one of notational con-venience: it applies to any 픾 when spanning trees and forests are produce for 픾̐.The nice things about Theorem 2.31 is not only that any spanning tree can beused, but also that the associated fundamental cycles can be found in time com-plexity  (| |2) [AMO93], which is independent of the size of the edge stacks in픾.The second cornerstone theorem describes the nature of connected componentsin feasible 퐴(픾).Theorem 2.32 (Layers and Sublayers). If 픾 is asingular and of size 푚, and if 퐴 isfeasible on 픾, then 퐴(픾) produces a set ℍ픾 of 푚 connected components 푖ℍ픾 ∶= {푖|푖 = 0, 1,… , 푚 − 1} (2.19)where each푖 is isomorphic to 픾. ℍ픾 are the layers of 퐴(픾) and푖 is the 푖th layerof 퐴(픾).If 픾 is singular or mixed, then any feasible 퐴(픾̐) produces |픾| regions 푖,each consisting of |푖| components isomorphic to 푖. The set ℍ푖 of connectedcomponents 푖푗 in 퐴(푖)ℍ푖 ∶= {푖푗|푗 = 0, 1,… , |푖| − 1} (2.20)are the layers of 퐴(푖), where 푖푗 is the 푗th layer of푖.For any connected stacked subgraph of a region푖, the set ℍ of connectedcomponents 푗 of 퐴()ℍ ∶= {푗|푗 = 0, 1,… , |푖| − 1} (2.21)are the sub-layers of 퐴(), where 푗 is the 푗th sub-layer of 퐴().18The number of fundamental cycles for a graph is derived in [AMO93].302.3. Assignments and FeasibilityProof. By Theorems 2.18 and 2.23, all feasible assignments on any 푛푚 or 푛푚produce푚 disjoint cycles or paths that are, by Corollaries 2.20 and 2.24, isomorphicto their parent object. The isomorphism proofs are by induction on the cycle andpath stacks of 픾 or its regions.Before ending this section, two more concepts will prove useful: assingularassignment constraints and regional stacked graphs.Definition 2.33 (Asingular Assignment Constraints). Let퐸푝푞 be asingular and퐴 anassignment on it. 퐴푝푞 is fully constrained if the values of all 푥푝푞푖푗 ∈ 퐴푝푞 are requiredto take specific value (i.e. they’re parameters and not variables). If only some arerestricted, then 퐴푝푞 is partially constrained. Otherwise, it is unconstrained.If 퐴 is an assignment on some 푛푚 so that all disjoint paths in 퐴(푛푚) are re-quired to start and end on specific vertices, then퐴(푛푚) is fully constrained. If onlysome are so required, then 퐴(푛푚) is partially constrained. Otherwise it is uncon-strained. If there are additional constraints on 퐴(푛푚) so that the paths of 퐴(푛푚)must pass through one or more additional, specific vertices, these are termed inter-nal constraints with the specified vertices called waypoints.Lemma 2.34 (Fully Constrained Asingular Cycle Stack Assignments). Assign-ments on asingular cycle stacks are fully constrained.Proof. See the proof of Theorem 2.23.Definition 2.35 (Regional Stacked Graphs ℝ픾). For any stacked graph 픾, the re-gional stacked graph of픾,ℝ픾, is the stacked graph formed by replacing each region푠 ∈ 픾 with a vertex stack 푉푠, where |푉푠| = |푠|. Edge stack 퐸푠푡 ∈ ℝ픾 existsonly if the singular boundary ̉푠푡 in 픾 is non-empty. Each vertex 푣푠푖 is associatedwith layer 푠푖 .Regional stacked graphs abstract the details of individual layers and focus onthe relationship between them. Paths in ℝ픾 represent broad-scale descriptions ofconnectedness between layers through regional boundaries.Figure 2.18 provides an example of regional stacked graphs using both packedand unpacked diagrams.Notice that the vertices in ℝ픾 represent abstract layers as layers are only prop-erly defined in the context of assignments (Theorem 2.32). The same theorem,however, tells us that, regardless of the assignment, we always know the numberof layers a feasible assignment will produce. We can therefore discuss layers in ageneral sense without the complexities involved when working with assignments.But what of assignments on ℝ픾? Since ℝ픾 is a stacked graph, we should beable to define assignments on it. While technically true, such assignment will be312.3. Assignments and Feasibility(a) (b)(c) (d)Figure 2.18: The (a) unpacked and (b) packed diagrams of some 픾 and its regionalstacked graph, as well as its (c) unpacked and (d) packed regional stacked graphℝ픾. 0 consists of edge stacks 퐸56 and 퐸67, 1 consists solely of 퐸34, and 2consists of 퐸01, 퐸12, and 퐸20. Singular boundary ̉01 in ℝ픾 consists of singularedges 퐸45 and 퐸47, while ̉12 consists only of 퐸23.322.4. Feasibility of Non-Simple Stacked Graphslargely meaningless. The value of 푥푟푡푖푗 ∈ 퐴(ℝ픾) for some 퐴 indicates whether layer푟푖 is adjacent to푡푗 through ̉푟푡, but little more; we know nothing of which verticesare in which layer.When we remember that ℝ픾 is a derived structure, it isn’t too hard to imaginethat derivatives of assignments can also be had.Definition 2.36 (Derived Assignments 퐴(ℝ픾)). Let 퐴 be a feasible assignment onsome 픾. Then 퐴(ℝ픾) is a derived assignment that can be defined in two ways:binary and proportional.In a binary assignment, for each 푒푟푡푖푗 ∈ 퐸푟푡, 퐸푟푡 ∈ ℝ픾, 푥푟푡푖푗 = 1 if there is atleast one vertex in 푟푖 adjacent to a vertex in 푡푗 , and 푥푟푡푖푗 = 0 if there isn’t. In theproportional assignment, 푥푟푡푖푗 is a proportional measure of such edges, defined by푥푟푡푖푗 ∶=||||{푥푎푏푐푑|||퐴푎푏 ∈ 퐴(̉푟푡), h(푣푎푐 ) = 푟푖 and h(푣푏푑) = 푡푗}||||||||{푥푎푏푐푑|||퐴푎푏 ∈ 퐴(̉푟푡), h(푣푎푐 ) = 푟푖}||||(2.22)where h(⋅) is the layer function which returns the layer of a vertex19.Binary assignments are used to indicate whether it’s possible to move directlybetween layers of adjacent regions. Proportional assignments give a measure ofhow likely such movement is as the ratio of the number of adjacencies that existbetween two layers of two adjacent regions to the total number of possible adja-cencies for the same layers. The proportional assignment 퐴(ℝ픾) is one instance ofwhere assignment flow values 푥푟푡푖푗 are non-binary.Note that in a binary assignment 푥푟푡푖푗 = 푥푡푟푗푖. This is not generally true in aproportional assignment. In Section 2.5 we introduce a technique for ensuring thatfeasible assignments are such that 퐴(ℝ픾) is always binary, the Uniform AdjacencyConstraint. There are theoretical reasons why binary assignments are desirable.These are discussed in Section 7.1 and Chapter 8.2.4 Feasibility of Non-Simple Stacked GraphsThe distinguishing characteristic between simple and non-simple stacked graphsis that non-simple stacked graphs contain loop stacks and multi-edge stacks, or cy-cle stacks of length one and two, respectively. Curiously, however, and much to oursatisfaction, little difference exists between the two from a feasibility perspective.19The function is undefined in the absence of an assignment.332.4. Feasibility of Non-Simple Stacked GraphsLemma 2.37 (Feasible Assignments on Loop Stacks). For any asingular stackedloop 퐸푝푝, or 1푚, the only feasible assignment 퐴푝푝 is such that퐴푝푝 ∶= {푒푝푝푖푖 |푖 = 0, 1,… , |퐸푝푝 − 1|}, (2.23)or 푥푝푝푖푗 = 1 if 푖 = 푗 and 푥푝푝푖푗 = 0 otherwise.Proof. 퐴푝푝 is feasible if 푣푝푖 and 푣푝푗 are disjoint when 푖 ≠ 푗. Thus 푒푝푝푖푗 ∉ 퐴푝푝 when 푖 ≠푗. Therefore, 퐴푝푝 can consists only of edges 푒푝푝푖푖 , which is a valid assignment.The assignment defined in Lemma 2.37 will play an important role throughoutthis work, and so is worthy of its own notation. Figure 2.19 illustrates the assign-ment.Definition 2.38 (Identity Assignment). For any asingular edge stack 퐸푝푞, the iden-tity assignment 퐴∗ is퐴∗푝푞 ∶= {푒푝푞푖푖 |푒푝푞푖푖 ∈ 퐸푝푞, 푖 = 0, 1,… , |퐸푝푞| − 1}, (2.24)or 푥푝푝푖푗 = 1 if 푖 = 푗 and 푥푝푝푖푗 = 0 otherwise. As 퐴∗ has the same construction for all퐸푝푞, the subscript of 퐴∗푝푞 can be dropped.Figure 2.19: The identity assignment 퐴∗.Lemma 2.39 (Feasible Assignments on Multi-Edge Stacks). Let 2푚 be the asin-gular cycle stack defined by 퐸푝푞 − 퐸푞푝. Then assignment 퐴 on 2푚 is feasible if푒푝푞푖푗 ∈ 퐴푝푞 ⟺ 푒푞푝푗푖 ∈ 퐴푞푝. (2.25)Equivalently, if 퐸푝푞 and 퐸′푝′푞′ are two different edge stacks between 푉푝 and 푉푞, then퐴푝푞 and 퐴′푝푞 are feasible if and only if 퐴푝푞 = 퐴′푝푞.342.5. Singular ConstraintsProof. The forward and backward components involve identical proofs. If 푒푝푞푖푗 ∈퐴푝푞 but 푒푞푝푗푖 ∉ 퐴푞푝, then 퐴(2푚) is not feasible as 푒푝푞푖푗 − 푒푝푞푗푘, 푘 ≠ 푗, is a path in퐴(2푚) so that 푣푝푖 and 푣푝푘 are not disjoint. Therefore, 푒푞푝푗푖 ∈ 퐴푞푝.Lemmas 2.37 and 2.39 lead directly to the following theorem concerning non-simple stacked graphs.Theorem 2.40 (Degeneracy of Non-Simple Stacked Graph Assignment Feasibil-ity). Let 픾 be an asingular, non-simple stacked graph. In addition, let 픾′ be thesub-graph of 픾 formed by removing all loop stacks and all but one edge stack inevery multi-edge stack. Then, for any feasible assignment 퐴′ on 픾′, there is exactlyone feasible assignment 퐴 on 픾 such that 퐴′ ⊂ 퐴.Proof. The only edges in 픾 that are not in 픾′ are those associated with loop andmulti-edge stacks. In addition, the only cycles in 픾 that are not in 픾′ are likewiseassociated with loop and multi-edge stacks. By Lemma 2.37, there is only onefeasible assignment on loop stacks, 퐴∗. Thus, if 픾′′ is the stacked graph formed byadding the loop stacks of 픾 to 픾′, there is only one feasible assignment 퐴′′ on 픾′′such that 퐴′ ⊂ 퐴′′.Similarly, let 퐸푝푞푖 be the 푖th edge stack for some multi-edge stack in 픾 and let퐸푝푞푘 be the one edge stack preserved in 픾′. Then, by Lemma 2.39, it must be thecase that 퐴푝푞푖 and 퐴푝푞푘 have the same structure for all 푖. Thus, if 픾′′′ is the stackedgraph formed by adding the multi-edge stacks of픾 not in픾′ to픾′, there is only onefeasible assignment 퐴′′′ on 픾′′′ such that 퐴′ ⊂ 퐴′′′.As 퐴′′ and 퐴′′′ are uniquely feasible and defined by 픾′′ and 픾′′′, it follows that퐴 ∶= 퐴′′ ∪ 퐴′′′ is the only feasible assignment on 픾 for which 퐴 ⊂ 퐴′.In short, Theorem 2.40 states that every asingular, non-simple stacked graphdegenerates into an asingular, simple stacked graph where finding feasible assign-ments on the latter immediately produces an associated - and unique - assignmenton the former. We can therefore ignore non-simple stacked graphs and focus ourattention solely on simple ones.2.5 Singular ConstraintsOur definition of assignment feasibility ignores singular edge stacks (Definition2.17). This does not imply that singularities are entirely free of constraints, however.There may be conditions on singular assignments which need to be met in order forthem to be considered feasible in the context of whatever problem is beingmodelledusing 픾.352.5. Singular ConstraintsThe assignment feasibility condition in Definition 2.17 is in a sense the basiccondition. It may be necessary to impose additional conditions to reflect known orsuspected relationships existing in the data that vertex stacks represent. To this end,we introduce non-basic singular feasibility constraints.Definition 2.41 (Non-Basic Singular Constraints). Let 퐸푝푞 ∈ 픾 be singular with|푉푝| > |푉푞|. A set of non-basic singular feasibility constraints on 퐸푝푞 define addi-tional restrictions that must be satisfied by any 퐴 on 퐸푝푞 for 퐴푝푞 to be consideredfeasible. Collapsing constraints define how 푉푝 maps to 푉푞, while expanding con-straints define the reverse, from 푉푞 to 푉푝. When both collapsing and expandingconstraints are part of the definition, then the constraint is mixed.If feasibility constraints are at least partially defined on labelled structures20,then they are labelled constraints, otherwise they are unlabelled constraints.If the same constraints are applied to every edge stack in 픾̉, then singular fea-sibility is consistent, otherwise it is inconsistent.If no additional constraints are used so that only that of Definition 2.17 hold,the singular feasibility constraints are considered basic.One such non-basic constraint is Uniform Layer Adjacency.Definition 2.42 (Uniform Layer Adjacency). Let 퐴 be an assignment 픾 with re-gions 푟 and 푡, |푟| > |푡|, and a non-empty ̉푟푡. The Uniform Layer Adja-cency constraint (ULA) requires that all vertices in the collapsing vertex stacks of퐴(̉푟푡) of the same layer must be adjacent to vertices in expanding vertex stacks allbelonging to the same, single layer.Formally, 퐴(̉푟푡) is feasible if for any 푥푐푑푎푏 = 1 in 퐴(̉푟푡) with 푣푐푎 ∈ 푟 and푣푑푏 ∈ 푡 such that h(푣푐푎) = 푟푥 and h(푣푑푏 ) = 푡푦 (2.26)thenh(푣푝푖 ) = 푟푥 and h(푣푞푗 ) = 푡푦 (2.27)for all 푥푝푞푖푗 = 1 with 푣푝푖 ∈ 푟 and 푣푞푗 ∈ 푡.The ULA constraint means that movement between layers through singularboundaries is consistent (Figure 2.20). It also plays nicely with derived assign-ments.Lemma 2.43. Feasible assignments 퐴 on 픾 satisfying the ULA constraint producederived assignments 퐴(ℝ픾) whose proportional and binary forms are identical.20Such as on specific vertex or (sub-)layer numbers.362.5. Singular Constraints(a) (b)Figure 2.20: Let 푉0 and 푉1 be of size 3 and in the same region 푟, 푉2 be size 2 in푡, and ̉푟푡 = {퐸02, 퐸13}. ULA requires that sub-layers in 푟 (blue, yellow, andred vertices) map uniformly to sub-layers in푡 (grey and green vertices). Both (a)and (b) are feasible assignments as (a) maps {blue, yellow} → green and {red} →grey, while (b) maps {yellow, red} → grey and {blue} → green.372.5. Singular ConstraintsProof. Either all vertices in푟푥 are adjacent to vertices in푡푦, or none are. Conse-quently, the set in the numerator of Equation 2.22 is the same as the denominatoror empty. The proportional measure 푥푟푡푖푗 is therefore either 0 or 1.38Chapter 3Stacked Graphs and SymmetricGroupsIn this chapter we explore the connection between stacked graphs and the sym-metric groups 핊푚, namely, how any desingularized stacked graph 픾̐ can be writtenas a system of group compositions, and vice versa. The relationship between sin-gular edge stacks and 핊푚 is not discussed in this work, being unimportant to theproject, but is certainly worthy of future considerationTo better reflect their connection with stacked graphs, group compositions ofthe form휎 ∗ 휏 ∗ 훼 ∗ 훽 (3.1)are read left to right, not right to left as is general practice. The basic properties anddefinitions of group theory below are based on [Fra03].3.1 Assignments and 핊푚The elements of symmetric group 핊푚 are defined as the 푚! permutations of 푚element, which we’ll take to be the first 푚 integers, including 0. Elements can berepresented in a two-line notation. For example, in휎 ∶=( 0 1 2 32 1 3 0), (3.2)where 휎 ∈ 핊4, the sequence0 1 2 3 (3.3)is permuted into2 1 3 0 (3.4)with 휎 mapping 0 to 2, 1 to 1, 2 to 3, and 3 to 0. These individual mappings arecalled transpositions. The transposition of 푎 with 푏 is written as(푎 푏) (3.5)393.1. Assignments and 핊푚with every element of 핊푚 capable of being written as a product of transpositions.For example휎 =( 0 1 2 32 1 3 0)= (11)(02)(03). (3.6)Theorem 3.1. [Fra03, Corollary 9.12] Any permutation of a finite set of at least 2elements can be written as a product of transpositions. [Corollary 9.12, Fraleigh]Permutations on 푚 elements can be viewed as perfect matching on the com-plete bipartite graph 푚푚21. This is equivalent to a bijection between two sets of 푚elements, or an automorphism on 푚 elements. Figure 3.1 illustrates 휎 as a perfectmatching on 44.Figure 3.1: The complete bipartite graph44 consists of every edge, thick and thin,while 휎 - a perfect matching or, in our case, bijective mapping of the left verticesto the right vertices - consists of only the thick lines. The matching is a graphicalrepresentation of the two-line permutation Equation 3.2.Clearly, there is a relationship between Figure 3.1 and our edge stacks and as-signments.Definition 3.2 (Edge Stack Group Duals). Let퐴 be an assignment on asingular퐸푝푞of size 푚. Then 퐴푝푞 is isomorphic to an element 훼푝푞 ∈ 핊푚. 퐴푝푞 is the (stacked)graph dual of 훼푝푞 and 훼푝푞 the (symmetric) group dual of 퐴푝푞. If no assignmentexist on 퐸푝푞, then group dual of 퐸푝푞 is denoted by 휖푝푞, where 휖푝푞 is an unidentifiedelement in 핊푚. Formally푒푝푞푖푗 ∈ 퐴푝푞 ⟺ (푖푗) ∈ 훼푝푞. (3.7)Every edge in an assignment is isomorphic to a transposition. If 푒푝푞푖푗 ∈ 퐴푝푞,then 푒푝푞푖푗 is the graph dual of transposition (푖푗) in 훼푝푞, which is denoted by 휖푝푞푖푗 .21Matchings on graphs are subsets of edges that are edge-independent (i.e. share no commonvertices) while perfect matchings are those that cover a graph’s vertex set [Fou92].403.1. Assignments and 핊푚If the transposition details of 훼푝푞 are unknown so that the value of 푗 is unknownin 휖푝푞푖푗 , then we define the 푖th transpose of 훼푝푞 to be 휖푝푞푖 , which always exists22. As휖푝푞 is a group element, 휖푝푞푖 is also used to indicated the (unknown) 푖th transpositionof 휖푝푞 23.The two-line notation of 훼푝푞 is written as훼푝푞 =(휈푝0 휈푝1 . . . 휈푝푚−1휈푞푤0 휈푤1 … 휈푞푤푚−1)(3.8)where 휈푝푖 and 휈푞푤푖 are the group duals of the vertices 푣푝푖 and 푣푞푤푖 in 푒푝푞푖푤푖 24. The groupduals of vertices are precisely the integers 0 through 푚 − 1휈푝푖 , 휈푞푤푖∈ {0, 1,… , 푚 − 1} (3.9)with 휈푝푖 = 휈푝푗 and 휈푞푤푖 = 휈푞푤푗 only when 푖 = 푗.Finally, the group dual of 푥푝푞푖푗 is denoted by 휒푝푞푖푗 .For every assignment 퐴푝푞 on an asingular edge stack, there is a correspondingsymmetric group element; for every edge in 퐴푝푞, a transposition. In light of Figure3.1, the isomorphisms are obvious enough to avoid a formal proof 25.The graph dual of 휎 (Figure 3.2) is identical to Figure 3.1, save for the vertexlabels.The two-line notation for group duals is cumbersome for general 훼푝푞. For aconcrete example, the two-line notation for 휎 is(휈푝0 휈푝1 휈푝2 휈푝3휈푞2 휈푞1 휈푞3 휈푞0). (3.10)Notice that the subscripts in Equation 3.10 are identical to the values in Equation3.2.The single most important group dual is, of course, the identity element, whoseassociated graph dual is a familiar one.22This is the group interpretation of the 푖th edge flow in Definition 2.15.23There is some abuse of notation here. Technically, 휖푝푞 should be 퐸푝푞 , or capital epsilon, sincegroup elements are sets of transpositions. However, we’ve intentionally restricted ourself to lower-case Greek letters for group theoretic concepts.24The group dual is Greek nu. The visual similarity is deliberate.25The relationship between perfect matchings and permutations is not novel to this work. However,I’ve been unable to locate existing literature generalizing the relationship to sequences of matchings- our ‘stacked’ graphs - and sequences of permutations, or compositions, in 핊푚. This chapter istherefore original, up to the knowledge of it’s author.413.1. Assignments and 핊푚Figure 3.2: To form a graph dual, 휎 requires - at this stage arbitrary - doublesubscripts. Thus if 휎 → 휎푝푞, the graph dual is 퐴푝푞.Fact 3.3. The identity element 휄 of 핊푚(0 1 . . . m-10 1 . . . m-1)(3.11)is the group dual of 퐴∗.A note of caution. The term 휖푝푞 represents an abstract element in 핊푚, or a setof unidentified transpositions. There are some difficulties with using 휖푝푞푖푗 and 휖푝푞푖 asit’s possible to write group elements as a product of transpositions (Theorem 3.1)in multiple ways. For example휏 ∶= (12)(35)can also be written as휏 = (12)(35)(46)(46).Transpositions (46)(46) - which together can represent the identity 휄 [Fra03] - arepart of the second representation of 휏, but not the first. The statement ‘transposition(푖푗) of 휎’, is therefore poorly defined. To correct this, we’ll assume that transpo-sition representations are minimal so that if 휎 ∈ 핊푚, exactly 푚 transposition arepresent, which may include one or more identities (푖푖) as in the case of 휎 in Equa-tion 3.6.Group duals can be extended to path and cycle stacks.Definition 3.4 (Duality of Path and Cycle Stacks). Let 푛푚 be the asingular pathstack 푛푚 ∶= 퐸01 − 퐸12 −⋯ − 퐸(푛−2)(푛−1). (3.12)423.1. Assignments and 핊푚The symmetric group dual of 푛푚 is the composition휋푛 ∶= 휖01 ∗ 휖12 ∗⋯ ∗ 휖(푛−2)(푛−1). (3.13)If 퐴 is an assignment on 푛푚 such that퐴(푛푚) = 퐴01 − 퐴12 −⋯ − 퐴(푛−2)(푛−1), (3.14)then the group dual of 퐴(푛푚) is the composition훼(휋푛) ∶= 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−2)(푛−1). (3.15)Similarly, for 푛푚 푛푚 ∶= 퐸01 − 퐸12 −⋯ − 퐸(푛−1)0, (3.16)the group dual of 푛푚 is the composition훿푛 ∶= 휖01 ∗ 휖12 ∗⋯ ∗ 휖(푛−1)0 (3.17)while the group dual of 퐴 on 푛푚 is the composition훼(훿푛) ∶= 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)0. (3.18)The stacked graph structures 푛푚 and 푛푚 are the (stacked) graph duals of 휋푛 and훿푛, respectively, while 퐴(푛푚) and 퐴(푛푚) are the (stacked) graph duals of 훼(휋푛)and 훼(훿푛), respectively.If the size of the symmetric group that each dual belongs to is important, groupduals of path and cycle stacks can be augmented to 휋푛푚 and 훿푛푚, respectively.Fact 3.5. Path stacks, cycle stacks, and assignments on them are isomorphic totheir group duals.While it is common practice to omit the operation symbol ∗, it will be main-tained here to emphasize the relation between path and cycle stacks with their groupcompositions as well as to space an otherwise cramped notation. The operationwill,however, be dropped when dealing with transpositions.As with퐸푝푞 and퐴푝푞, it’s important to stress the difference between 휖푝푞 and 훼푝푞:휖푝푞 is an unspecified element in 핊푚 while 훼푝푞 is a particular value that 휖푝푞 takes on.If 휋푛 is the group dual of 푛푚 and 훼(휋푛) the group dual of an assignment퐴 on 푛푚,the underlying structure of 훼(휋푛) is defined by 휋푛; 훼(휋푛) is a particular valuationof 휋푛.This highlights a key conceptual difference between stacked graphs and theirgroup duals: even when there is no assignment on some 퐸푝푞, there is an implicit,unknown assignment associated with 휖푝푞. There is always a perfect matching orset of network flows 푥푝푞푖푗 associated with some 휖푝푞, which is not the case with edgestacks. This, as we’ll soon see, is a wonderful property.Being elements of a group, group duals have inverses.433.1. Assignments and 핊푚Theorem 3.6 (Inverse of Edge Stack Group Duals). Let 퐴 be an assignment onsome asingular 퐸푝푞. Then the inverse of its group dual 훼푝푞 is 훼푞푝. That is,훼−1푝푞 = 훼푞푝.Proof. Let |퐸푝푞| = 푚. The edge set of 퐴푝푞 is a vertex disjoint set{푒푝푞푖푗 |푖, 푗 = 0, 1,… , 푚 − 1} (3.19)while that of 퐴푞′푝′ is{푒푞′푝′푖푗 |푖, 푗 = 0, 1,… , 푚 − 1} (3.20)with 푒푞′푝′푖푗 = 푒푞푝푗푖 26. As a result, the path stack퐸푝푞 − 퐸푞′푝′ (3.21)has the assignment퐴푝푞 − 퐴푞′푝′ , (3.22)where each disjoint path 푃푖 is of the form 푒푝푞푖푗 −푒푞′푝′푗푖 , which is equivalent to 푒푝푞푖푗 −푒푞푝푗푖 .An example of this is shown in shown in Figure 3.3. In two-line notation, the groupdual of 퐴푝푞 − 퐴푞′푝′ is훼푝푞 ∗ 훼푞′푝′ =(휈푝0 . . . 휈푝푚−1휈푞푤0 . . . 휈푞푤푚−1)∗(휈푞′0 . . . 휈푞′푚−1휈푝′푤0 . . . 휈푝′푤푚−1)(3.23)=(휈푝0 . . . 휈푝푚−1휈푞푤0 . . . 휈푞푤푚−1)∗(휈푞푤0 . . . 휈푞푤푚−1휈푝0 . . . 휈푝푚−1)(3.24)=(휈푝0 . . . 휈푝푚−1휈푝0 . . . 휈푞푚−1)(3.25)or the identity element 휄. Therefore 훼−1푝푞 = 훼푞푝.Implicit in Theorem 3.6, which also applies to unassigned 퐸푝푞 and its dual 휖푝푞,is that while stacked graphs can often be treated as undirected, group duals treatthem as inherently directed, with inverses denoting changes in direction.Theorem 3.7 (Inverse of Path Stack Group Duals). If 퐴 is an assignment on 푛푚so that퐴(푛푚) = 퐴01 − 퐴12 −⋯ − 퐴(푛−1)푛 (3.26)26Primes are introduced to prevent 퐸푝푞 − 퐸푞′푝′ from being a pair of parallel edges between 푉푝 and푉푞 .443.1. Assignments and 핊푚Figure 3.3: An example of 퐴푝푞 − 퐴푞′푝′ where |퐸푝푞| = 4.with group dual훼(휋푛) = 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)푛 (3.27)then the inverse of 훼(휋푛) is the group dual of퐴(̄푛푚) = 퐴푛(푛−1) −⋯ − 퐴21 − 퐴10, (3.28)or훼(휋̄푛) = 훼푛(푛−1) ∗⋯ ∗ 훼21 ∗ 훼10, (3.29)where ̄푛푚 is 푛푚 in the opposite direction.Proof. For any composition 훼 ∗ 훽, the inverse of 훼 ∗ 훽 is 훽−1 ∗ 훼−1 [Rom12].Thus the inverse of 훼(휋푛) is훼(휋푛)−1 = 훼−1(푛−1)푛 ∗⋯ ∗ 훼−112 ∗ 훼−101 . (3.30)By Theorem 3.6, we have훼−1(푛−1)푛 ∗⋯ ∗ 훼−112 ∗ 훼−101 = 훼푛(푛−1) ∗⋯ ∗ 훼21 ∗ 훼10 (3.31)so that훼(휋푛)−1 = 훼(휋̄푛) (3.32)with훼(휋푛) ∗ 훼(휋̄푛) = 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)푛 ∗ 훼푛(푛−1) ∗⋯ ∗ 훼21 ∗ 훼10= 휄. (3.33)453.1. Assignments and 핊푚Theorem 3.8 (Inverse of Cycle Stack Group Duals). If 퐴 is an assignment on 푛푚so that퐴(푛푚) = 퐴01 − 퐴12 −⋯ − 퐴푛0 (3.34)with group dual훼(훿푛) = 훼01 ∗ 훼12 ∗⋯ ∗ 훼푛0 (3.35)then the inverse of 훼(훿푛) is the group dual of퐴(̄푛푚) = 퐴0푛 −⋯ − 퐴21 − 퐴10, (3.36)or훼(훿̄푛) = 훼0푛 ∗⋯ ∗ 훼21 ∗ 훼10, (3.37)where ̄푛푚 is 푛푚 in the opposite direction.Proof. The proof is similar to that of Theorem 3.7.The double indices imposed on group duals by their stacked dual counterpartsrestricts right and left composition of additional elements. For example, given휖45 ∗ 휖57 ∗ 휖73 = 훽 (3.38)for some 훽 ∈ 핊푚, one can normally compose both sides by the same arbitraryelement휖45 ∗ 휖57 ∗ 휖73 ∗ 휖89 = 훽 ∗ 휖89 (3.39)without changing the relationship between the left and right sides of the equation.Unfortunately, the left side of Equation 3.39 is not a group dual for any path stackas 휖73 and 휖89 don’t share an intervening index (Figure 3.4).Figure 3.4: The graph dual of 휖45 ∗ 휖57 ∗ 휖73 ∗ 휖89 is not a path stack.In general, group dual compositions cannot be operated on arbitrarily sincegroup elements represent edge stacks: pre-pending or appending elements to agroup dual composition is equivalent to either changing the connectivity or addingedge stacks to the corresponding stacked dual. There is, however, a notable excep-tion.463.1. Assignments and 핊푚Definition 3.9 (Cyclicity Condition). A composition휋푛 ∶= 휖푤0푤1 ∗ 휖푤1푤2 ∗⋯ ∗ 휖푤푛−1푤푛 (3.40)satisfies the cyclicity condition if 푤푛 = 푤0 and휖푤0푤1 ∗ 휖푤1푤2 ∗⋯ ∗ 휖푤푛−1푤푛 = 휖푤1푤2 ∗ 휖푤2푤3 ∗⋯ ∗ 휖푤푛−1푤푛 ∗ 휖푤0푤1= 휖푤2푤3 ∗ 휖23푤4 ∗⋯ ∗ 휖푤푛−1푤푛 ∗ 휖푤0푤1 ∗ 휖푤1푤2⋮= 휖푤푛푤0 ∗ 휖푤0푤1 ∗ 휖푤1푤2 ∗⋯ ∗ 휖푤푛−1푤푛 . (3.41)If 휋푛 satisfies these conditions, then it is a cyclic composition. Otherwise it is apath composition. The compositions above are the cyclic forms of 휋푛.Similarly, 훼(휋푛) is cyclic if훼푤0푤1 ∗ 훼푤1푤2 ∗⋯ ∗ 훼푤푛−1푤푛 = 훼푤1푤2 ∗ 훼푤2푤3 ∗⋯ ∗ 훼푤푛−1푤푛 ∗ 훼푤0푤1= 훼푤2푤3 ∗ 훼23푤4 ∗⋯ ∗ 훼푤푛−1푤푛 ∗ 훼푤0푤1 ∗ 훼푤1푤2⋮= 훼푤푛푤0 ∗ 훼푤0푤1 ∗ 훼푤1푤2 ∗⋯ ∗ 훼푤푛−1푤푛 . (3.42)Lemma 3.10 (Inverse of Cycle Stack Group Duals). Let 휋푛 be a cyclic compositionand 휋푛푖 be one of its cyclic forms. Then the inverse of 휋푛푖 is 휋̄푛푖 .Proof. The proof involves the application of Theorem 3.7 to each cyclic form 휋푛푖 .Group duality can be generalize to entire stacked graphs.Definition 3.11 (Group Dual of 픾). Let 픾 be asingular and defined by a collectionof 푘 asingular path and cycle stacks 푖 and 푗 , each possibly of different length,such that the union of their edge stack sets is  of 픾 27. Then the vector훾 ∶=< 훾0, 훾1,… , 훾푘 > (3.43)is the (symmetric) group dual of 픾, the system of compositions 훾푟 where each 훾푟 isthe group dual of a unique 푖 or 푗 .If 훾 is the group duals of 픾, then 픾 is the (stacked) graph dual of 훾 .Similarly, if 픾 is not asingular, then 픾̐ and 훾̐ are duals of each other.27Each 푖 and 푗 need not be disjoint on their edge stacks.473.2. Assignment Feasibility and Symmetric Group DualsThe key differences between 픾 and 픾̐ is that each composition 훾̐푖 in 훾̐ may be-long to symmetric groups of different sizes, depending on the size of each asingularpath and cycle stack. For mixed 픾, 픾̐ is a forest, in which case each composition 훾̐푖of different sized groups will share no group elements in common. In this case, 픾̐and 훾̐ are better treated on a regional basis, namely in terms푖 and their associatedgroup duals.The group duals of singular edge stacks aremappings between symmetric groupsof different sizes. While undoubtedly important, they are not necessary for ourproject and would be an unprofitable digression. We’ll leave treatment of them fora future work.3.2 Assignment Feasibility and Symmetric Group DualsWe now turn to the group dual equivalent of feasibility.Definition 3.12 (Constrained Group Duals). If an assignment퐴 on asingular퐸푝푞 isfully constrained (Definition 2.33) to be퐴′, so that퐴푝푞 = 퐴′푝푞, then the (symmetric)group dual constraint of 퐴푝푞 is 훽푝푞, with훽푝푞 ∶= 훼′푝푞. (3.44)Similarly, let 퐴 be an assignment on 푛푚 with푛푚 = 퐸01 − 퐸12 −⋯ − 퐸(푛−1)푛. (3.45)If 퐴(푛푚) is fully constrained so that each path 푃푖 starting on 푣0푖 must end on aspecific 푣푛푤푖 , then the group dual constraint is 훽훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)푛 = 훽, (3.46)where 훽 is defined to be (휈00 . . . 휈푛푚−1휈0푤0 . . . 휈푛푤푚−1). (3.47)If 퐴(푛푚) is unconstrained, then 훽 is free and can be any element in 핊푚. If퐴(푛푚) partially constrained so that 훽 is restricted to a subset of 핊푚, then 훽 isrestricted. Otherwise, 훽 is bound.Fact 3.13 follows directly from Lemma 2.34 and the definition of constrainedgroup duals.483.2. Assignment Feasibility and Symmetric Group DualsFact 3.13. The group dual constraint 훽 of any cycle stack assignment 퐴(푛푚) isbound.We next introduce paths defined by transpositions.Definition 3.14 (Transposition Paths). Let 훼(휋푛) be the group dual of some퐴(푛푚)훼(휋)푛 = 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)푛. (3.48)Each 훼푝푞 consists of 푚 transpositions of the form (휈푝푖 휈푞푗 ), where 휈푝푖 and 휈푞푗 are ver-tex group duals. Let the succession of transpositions starting in 훼01 and ending in훼(푛−1)푛 taking 휈0푖 to some 휈푛푤푛(휈0푖 휈1푤1)(휈1푤1휈2푤2)… (휈푛−1푤푛−1 , 휈푛푤푛) (3.49)where푤푘 = 0, 1,… , 푚−1, be the 푖th transposition path 휋푖 of 훼(휋푛). 휋푖 is the groupdual of 푃푖, the 푖th disjoint path in 퐴(푛푚) (Theorem 2.18).Similarly, if 훼(훿푛) is the group dual of some 퐴(푛푚)훼(훿)푛 = 훼01 ∗ 훼12 ∗⋯ ∗ 훼(푛−1)0, (3.50)the 푖th transposition cycle 훿푖 of 훼(훿푛) is(휈0푖 휈1푤1)(휈1푤1휈2푤2)… (휈푛−1푤푛−1휈0푤0). (3.51)훿푖 is the group dual of 퐶푖, the 푖th disjoint cycle in 퐴(푛푚) (Theorem 2.23).As 휋푛 and 훿푛 are compositions of elements, whatever those elements may be,transposition paths are likewise defined on them.The dualities between 휋푖 and 푃푖, 훿푖 and 퐶푖, are intuitively clear and should notrequire proof. However, the follow lemma is included to further emphasize therelationship between the two.Lemma 3.15. For any 휋푛 or 훼(휋푛) in 핊푚, there are exactly 푚 transposition pathswhich form a disjoint cover of their vertex group duals. That is, every 휈푗푖 in 휋푛 or훼(휋푛) is in exactly one of 푚 transposition path 휋푘 or 훼(휋푘).Proof. We prove this in the case of 휋푛. The case of 훼(휋푛) is identical. Let휋푛 = 휖01 ∗ 휖12 ∗⋯ ∗ 휖(푛−1)푛. (3.52)Every 휖푝푞 is an element in some 핊푚, and therefore a one-to-one, onto mappingexists from the vertex group duals 휈푝푖 , 푖 = 0, 1,… , 푚− 1, to 휈푞푗 , 푗 = 0, 1,… , 푚− 1.493.2. Assignment Feasibility and Symmetric Group DualsThis can be written as a collection of transpositions of the form (휈푝푖 휈푞푗 ), where eachvertex group dual belongs to a single transposition. If 푛 = 1, then the transpositionpaths are of length one and form a cover of 휋푛. If 푛 ≥ 2, then 휋푛 is a successionof these one-to-one mappings. Since each transposition path consists of adjacenttranspositions of the form(휈푟−1푖 휈푟푗 )(휈푟푗휈푟+1푘 ) (3.53)or, more generally, mappings of the form휈푟−1푖 → 휈푟푗 → 휈푟+1푘 (3.54)it follows that every vertex group dual belongs to exactly one transposition path.That there are 푚 transition paths follows directly from the bijective nature of themapping.Lemma 3.15 is the group dual interpretation of Theorem 2.18. The group dualconstraints for cyclic compositions are special.Theorem3.16 (Cyclic Compositions andConstraints). For every constrained cycliccomposition 훿푛+1 = 훽, 훽 = 휄 for all 푛 ≥ 0.Proof. Let훿푛+1 ∶= 휖01 ∗ 휖12 ∗⋯ ∗ 휖푛0 (3.55)where the 푖th transposition cycle 훿푖 is(휈0푖 휈1푤1)(휈1푤1휈2푤2)… (휈푛푤푛휈0푤0). (3.56)As 훿푛+1 has 푛 + 1 equivalent, cyclic forms휖01 ∗ 휖12 ∗⋯ ∗ 휖(푛−1)푛휖푛0휖12 ∗ 휖23 ∗⋯ ∗ 휖푛0 ∗ 휖01휖23 ∗ 휖34 ∗⋯ ∗ 휖01 ∗ 휖12⋮휖푛0 ∗ 휖12 ∗⋯ ∗ 휖(푛−2)(푛−1) ∗ 휖(푛−1)푛, (3.57)훿푖 also has 푛 + 1 equivalent forms, namely(휈0푖 휈1푤1)(휈1푤1휈2푤2) … (휈푛−1푤푛−1휈푛푤푛)(휈푛푤푛휈0푤0)(휈1푤1휈2푤2)(휈2푤2휈3푤3) … (휈푛푤푛휈0푤0)(휈0푖 휈1푤1)(휈2푤2휈3푤3)(휈3푤3휈4푤4) … (휈0푖 휈1푤1)(휈1푤1휈2푤2)⋮(휈푛푤푛휈0푤0)(휈0푖 휈1푤1) … (휈푛−2푤푛−2휈푛−1푤푛−1)(휈푛−1푤푛−1휈푛푤푛). (3.58)503.2. Assignment Feasibility and Symmetric Group DualsHowever, the forms of 훿푖 collapse, respectively, into(휈0푖 휈0푤0)(휈1푤1휈0푤0)(휈0푖 휈1푤1)(휈2푤2휈0푤0)(휈0푖 휈2푤2)⋮(휈푛푤푛휈0푤0)(휈0푖 휈푛푤푛). (3.59)Due to the subscript constraints placed on group duals by their stacked counterparts(Figure 3.4), it must be the case that 푤0 = 푖. Thus the forms further collapse intothe identity transpositions(휈1푤1휈1푤1)(휈2푤2휈2푤2)⋮(휈푛푤푛휈푛푤푛). (3.60)This applies to all transposition paths, implying that훿푛+1 = 휖01 ∗ 휖12 ∗⋯ ∗ 휖푛0 = 훽 = 휄 (3.61)and that the group dual constraint of each cyclic form of 훿푛+1 is also 휄. Therefore훽 = 휄.This leads to the following important theorem relating assignment feasibilityand group duals.Theorem 3.17 (Feasible Cycle Stack Assignments and Group Duals). Let 훿푛+1 bethe group dual of (푛+1)푚. Then 훼(훿푛+1) is cyclic if and only if its stacked dual퐴((푛+1)푚) is feasible.Proof. For the forward component, a feasible 퐴((푛+1)푚) consists of 푚 disjoint cy-cles 퐶푖, each with a group dual of the form(휈0푖 휈1푤1)(휈1푤1휈2푤2)… (휈푛푤푛휈0푖 ) (3.62)By reasoning similar to that of the forward component of the proof for Theorem3.16, we can show that훼(훿푛+1) = 훽 = 휄 (3.63)and that 훽 = 휄 for every cyclic forms of 훼(훿푛+1). Therefore, by Theorem 3.16,훼(훿푛+1) is cyclic.513.2. Assignment Feasibility and Symmetric Group DualsFor the backward component, by the proof of Theorem 3.16, each transpositionpath 훿푖 of 훼(훿푛+1) must take the form훿푖 = (휈0푖 휈1푤1)(휈1푤1휈2푤2)… (휈푛푤푛휈0푖 ) (3.64)so that the graph dual of 훿푖 is some cycle 퐶푖 in 퐴((푛+1)푚) of length 푛 + 1퐶푖 = 푒01푖푤1 − 푒12푤1푤2−⋯ − 푒푛0푤푛푖. (3.65)Therefore, as there are 푚 transposition paths of length 푛 + 1 (Lemma 3.15), and so푚 cycles of length 푛 + 1, by Theorem 2.23 퐴((푛+1)푚) is feasible.This is the primary benefit of working with group duals: feasibility of cyclestack assignments are maintained by requiring that their group dual constraints bethe identity element.Assignment duals are easily extended to entire stacked graphs.Definition 3.18 (Group Dual of 퐴(픾)). Let 픾 be asingular and defined by a col-lection of 푘 asingular path and cycle stacks 푖 and 푗 , of which each may be ofdifferent length, such that the union of their edge stack sets is  of 픾, and let 훾 beits group dual. Then, if 퐴 is an assignment on 픾, the vector훼(훾) ∶=< 훼(훾0), 훼(훾1),… , 훼(훾푘) > (3.66)is the (symmetric) group dual of 퐴(픾), the system of compositions 훼(훾푖), for all 훾푖in 훾 . If 훼(훾) is the group duals of 퐴(픾), then 퐴(픾) is the (stacked) graph dual of훼(훾).The constrained group dual of 퐴(픾) is the vector훽 ∶=< 훽0, 훽1,… , 훽푘 >, (3.67)with 훽푖 the group dual constraint of 훼(훾푖), such that훼(훾) = 훽. (3.68)Similarly, if 픾 is not asingular, then 훼(픾̐) and 훼(훾̐) are duals of each other with훽̐ the group dual constraint.Included in the constrained group dual are all fully and partially constrainededge stack group duals 훼푖푗 , so that훼푖푗 ∈ 훽푖푗 , (3.69)where 훽푖푗 is the subset of 핊푚 elements that 훼푖푗 is restricted to. In the presence ofnon-free compositions, the notation 훼(훾) = 훽 is one of convenience since the usageof ‘=’ is not strictly correct.The following two theorems and single definition reformulate the key findingsregarding assignment feasibility in terms of graph duals.523.2. Assignment Feasibility and Symmetric Group DualsTheorem 3.19 (Feasible Assignments and Group Duals). Let픾 be asingular and퐴an assignment on it, and 훾 and 훼(훾) their respective group duals, where 훾 includesthe graph dual of every cycle stack in 픾. Then, 퐴(픾) is feasible if and only if, forevery 훿 in 훾 , 훼(훿) is cyclic.Proof. By Theorem 3.17 every cycle composition 훼(훿) in 훼(훾) has a feasible graphdual in 퐴(픾) and every feasible cycle stack assignment 퐴(푛푚) in 퐴(픾) has cyclicgroup dual 훼(훿). By Theorem 2.25, 퐴(픾) is therefore feasible and every 훼(훿) iscyclic.Definition 3.20 (Fundamental Forms of Group Duals). Let 픾 be asingular, 퐴 afeasible assignment on it, and 핋 a spanning tree stack of 픾. Then the group dual 훾of 픾 is in fundamental form if its path compositions 휋푖 are formed solely on edgestacks in 픾̃ while its cyclic compositions 훿푖 are formed solely by the fundamentalcycle stacks in 핋 .If 픾 is not asingular, then fundamental forms are based on the fringe and fun-damental cycles of 픾̐.Theorem 3.21 (Feasible Assignments and Fundamental Forms). Let 훾 be the groupdual of some 픾 in fundamental form. Then an assignment 퐴 on 픾 is feasible if andonly if, for every 훿푖 in 훾 , the group dual 훼(훿푖) is cyclic, or, equivalently by Theorem3.16, if 훼(훿푖) = 휄.Proof. The proof follows directly from Theorems 2.31 and 3.19.Theorems 3.19 and 3.21 have rather profound implication. Group duals, inparticular those in a fundamental form, provide a means of representing the struc-ture of stacked graphs while preserving assignment feasibility in an elegant form.We are no longer forced to deal with edges, vertices, and network flow values, onlygroup elements and transposition. We also now have access to group theoretic toolswith which to study feasibility, and which may provide more efficient optimizationtechniques than the LP formulation described in Chapter 4 to find the best feasibleassignment for a given픾. Conversely, graph duals introduce a method of modellingat least one class of group theoretic problems in terms of graphs and network flows.Most forms of problemmodelling using stacked graphswill likely involveweightededges, edge stacks, and assignments.Definition 3.22 (Weighted Stacked Graphs, Assignments, and Group Duals). Forany stacked graph 픾, a weighting of 픾 assigns, to each 푒푝푞푖푗 ∈ 픾, a real-valuedweight 푤푝푞푖푗 . For any assignment 퐴 on 퐸푝푞, the weight of 퐴푝푞 is푤(퐴푝푞) ∶=∑푒푝푞푖푗 ∈퐸푝푞푤푝푞푖푗 푥푝푞푖푗 (3.70)533.3. Duality and Non-Simple Stacked Graphswhere 푥푝푞푖푗 is the flow value of 푒푝푞푖푗 under 퐴푝푞 (Definition 2.15). The weight of anassignment 퐴 on 픾, feasible or otherwise, is푤(퐴(픾)) ∶=∑퐴푝푞∈퐴(픾)푤(퐴푝푞) =∑퐸푝푞∈픾∑푒푝푞푖푗 ∈퐸푝푞푤푝푞푖푗 푥푝푞푖푗 . (3.71)If 훼푝푞 is the group dual of some 퐴푝푞, the weight of transposition (푖푗) is푤((푖푗)) ∶= 푤푝푞푖푗 (3.72)while the weight of 훼푝푞 is푤(훼푝푞) ∶=∑(푖푗)∈훼푝푞푤((푖푗)) = 푤(퐴푝푞) (3.73)3.3 Duality and Non-Simple Stacked GraphsIn Section 2.4we looked at assignment feasibility for loop andmulti-edge stacks,concluding that the only feasible assignment for the former is the identity assign-ment 퐴∗ (Lemma 2.37). For the latter, all feasible assignments on some 퐸푝푞 −퐸푞푝are of the form 퐴푝푞 − 퐴푞푝 (Lemma 2.39). The graph duals of both non-simplestructures satisfy similar constraints.Lemma 3.23. The group dual to any feasible assignment 퐴 on a loop stack 퐸푝푝 is휄.Proof. See Fact 3.3.Lemma 3.24. Let 퐸푝푞푖 and 퐸푝푞푗 be any two edge stacks between vertex stacks 푉푝and 푉푞, so that they form a multi-edge stack. The group duals to any feasible as-signments on 퐸푝푞푖 and 퐸푝푞푗 are푎푝푞푖 = 푎푝푞푗 ∀ 푖, 푗. (3.74)That is, if assignments on multi edge stacks are feasible, then each has identicalassignments.Proof. This follows directly from Lemma 2.39.Group duals of non-simple stacked graphs degenerate to group duals of simplestacked graphs.543.3. Duality and Non-Simple Stacked GraphsTheorem 3.25. Let 픾 be an asingular, non-simple stacked graph with group dual훾 . In addition, let 픾′ be the sub-graph of 픾 formed by removing all loop stacks andall but one edge stack in every multi-edge stack, and let 훾 ′ be it’s group dual. Thenthe group dual 훼′(훾 ′) of any feasible assignment of 퐴′ on 픾′ generates a uniquegroup dual 훼(훾).Proof. The proof is similar to that of Theorem 2.40: the only group dual of feasibleassignments on loop stacks is 휄 (Lemma 3.23) while the group dual of a single edgestack 훼푝푞푘 in multi-edge stack generates the (unique) group dual of each other 훼푝푞푖(Lemma 2.39).55Chapter 4Linear Programming:Communication, Capacity, andContiguityIn this chapter, we construct a linear program (LP) which satisfies the con-straints of Theorem 2.31 and whose optimal solution is a minimally weighted fea-sible assignment. A basic knowledge of linear programming and network flows isassumed.Let 픾 be a weighted stacked graph. An assignment 퐴 on 픾 is optimal if itprovides a solution to the following objective functionmin∑퐴푝푞∈퐴(픾)∑푒푝푞푖푗 ∈퐸푝푞푤푝푞푖푗 푥푝푞푖푗 (4.1)with 푥푝푞푖푗 ∈ {0, 1}, which will be shorthanded tomin∑푤푝푞푖푗 푥푝푞푖푗 . (4.2)Before we discuss the linear constraints that apply Equation 4.1, we should notethat there are different ‘scales’ of ‘levels’ of optimization that can be conducted.Given the size of 픾 and its relative complexity in terms of number of layers, re-gions, and proportion of singular to asingular edge stacks, any one of three generaloptimization approaches can be used: local, regional, or global.4.1 Local, Regional, and Global OptimizationLocal optimization involves finding minimal weightings to each singular andasingular edge stack assignments 퐴푝푞 independent of all others. It is equivalent tosolving a collection of bipartite matching problems, for which there exist network-flow algorithms far more efficient than a standard LP formulation [AMO93]. Aseach퐴푝푞 is independent, assignments can be solved in parallel. The difficulty is that564.2. The 3C Constraints of Assignment Feasibilitythe set of edge stack assignments, taken as the definition for a single assignment on픾, may not be feasible.Regional optimization refers to optimizing over the regions 픾 of 픾. Regionalassignments 퐴(푖) for each 푖 ∈ 픾 are solved for independently, as with localoptimization. The key difference is that assignment feasibility needs to be consid-ered: at the local level, assignments are on path stacks of length one and so allassignments are feasible (Corollary 2.19), where this is rarely the case at the re-gional level. Assignments on asingular edge stacks are solved for individually andindependently, as at the local level.The last level of optimization, global, solves the entirety of퐴(픾) at once - every퐴푝푞 is solved for simultaneously, including asingular edge stacks, and any non-basicsingular constraints are enforced (Definition 2.41).If singularity constraints are basic and either regional or global optimization isused, the process can be reduced to three distinct, independent stages: local sin-gular, local fringe, and core. Local singular applies local optimization to each퐸푝푞 ∈ 픾̉, local fringe does the same for 픾̃, while core optimizes over the funda-mental cycles in 픾̊. The partitions of  for any 픾 (Lemma 2.14) thus partition theoptimal feasible assignment problem.In general, only global optimization is guaranteed to yield an optimal solutionto Equation 4.1. However, local and regional approaches are expected to be fasterand, depending on the structure of 픾 and underlying problem, produce result that,if not optimal, may near enough to optimality to be useful. In the LP constructsbelow, local core optimization is conducted first, followed by the ULA non-basicconstraint.4.2 The 3C Constraints of Assignment FeasibilityThere are three kinds of linear constraints required to ensure assignment feasi-bility on asingular stacked graphs, such as 픾̊: communication, capacity, and con-tiguity. Communication refers to where the disjoint paths of a feasible assignmenton path and cycle stacks start and stop, also known as asingular constraints (Def-inition 2.33). As 퐴(푛푚) is fully constrained for every 푛푚 (Lemma 2.34), everypath in 퐴(퐶푛푚) must start and end on the same vertex. In effect, any start vertex‘communicates’ with itself. For any path stack 푛푚, the start and end vertices ofthe connected components of 퐴(푛푚) may or may not be different. In our LP con-struction, we shall assume that path stacks are unconstrained, as constraints are notrequired for feasibility.The necessity that connected components of feasible assignments are disjointrequires that each edge in an edge stack has a ‘capacity’ of 1 [AMO93]. Path and cy-574.2. The 3C Constraints of Assignment Feasibility(a) (b)Figure 4.1: 32 as (a) a standard cycle stack and (b) as a linear cycle stacks 32퐿 .cle stacks that are joined (Theorem 2.27) are required to have identical assignmentswhere they are ‘contiguous’.The linear constraints for communication, capacity, and contiguity are describedbelow. In their constructions, we treat cycle stacks as a variation of a path stack.These linear cycle stacks are easier to read from a diagrammatic perspective andillustrate how communication constraints can be put on path stacks.Definition 4.1 (Linear Cycle Stacks). For any asingular cycle stack푛푚 = 퐸푎푏 − 퐸푏푐 −⋯ − 퐸푦푧 − 퐸푧푎 (4.3)split 푉푎 into two vertex stacks 푉푎′ and 푉퐿, so that 퐸푎푏 becomes 퐸푎′푏 and 퐸푧푎 be-comes 퐸푧퐿. This converts 푛푚 into푛푚퐿 ∶= 퐸푎′푏 − 퐸푏푐 −⋯ − 퐸푦푧 − 퐸푧퐿, (4.4)where 푛푚퐿 is a linear cycle stack, specifically, the linearisation of 푛푚. If 퐴 is anassignment on 푛푚퐿 , then 퐴(푛푚퐿 ) is defined to be feasible if 푣푎′푖 is path connected to푣퐿푗 for all 푖 = 푗 and disconnected for all 푖 ≠ 푗.The weight of 푒푎′푏푖푗 and 푒푧퐿푖푗 are푤푎′푏푖푗 = 푤푎푏푖푗 and 푤푧퐿푖푗 = 푤푧푎푖푗 . (4.5)Figures 3.3 and 4.1 demonstrate linear cycle stacks.The definition of feasibility for linear cycle stacks satisfies Theorem 2.23 and isa special case of Theorem 2.19. Assignments on linear cycle stacks are an exampleof fully constrained path stack assignment (Definition 2.33).584.2. The 3C Constraints of Assignment FeasibilityIn what follows, we’ll assume that a spanning tree stack 핋 has been found for픾̊ as well as a cycle stack basis 핋 , and that each cycle stack is in 핋 . Thoughdiscussed in the context of a single cycle stack 푛푚, the constraints below apply toevery cycle stack in 핋 .4.2.1 CommunicationFor 퐴(퐶푛푚퐿 ) to be feasible, a path must exist between 푣푎′푖 and 푣퐿푖 . As we’relooking for minimally weighted paths, the condition can be modelled as a minimalpath length LP problem, treating 푣푎′0 as the source vertex and 푣퐿0 as the sink vertex[AMO93]푚−1∑푗=0푥푝푞푖푗 −푚−1∑푗=0푥푞푝푗푖 =⎧⎪⎨⎪⎩1, if 푖 = 0 and 푝 = 푎′−1, if 푖 = 0 and 푞 = 퐿0, otherwise, (4.6)∀푖 ∈ 0,… , 푚 − 1, ∀퐸푝푞 ∈ 푛푚퐿 .The same is true for the remaining 푚− 1 paths. Modelling distinct source-sinkpairs on a single network is problematic: if paths are not disjoint, then informationconcerning where each path starts and stops is lost (Figure 4.2).Figure 4.2: The four shortest paths for some 44. Although the blue and red pathsshare edge 푒1210, by backtracking from 푣퐿1 and 푣퐿2 it’s possible to extract both paths.In the case of path components 푒1221 − 푒2312 and 푒1223 − 푒2332, this is not possible: whichis black and which yellow?Path information can be maintained by treating paths as distinct commoditiesin a multi-commodity flow problem [AMO93]. To keep things simple and uni-commodity, we’ll instead create푚 identical instances of 푛푚 (and therefore of 푛푚퐿 ),one for each path, and model a shortest path algorithm on each.594.2. The 3C Constraints of Assignment Feasibility푚−1∑푗=0푥푘 푝푞푖푗 −푚−1∑푗=0푥푘 푞푝푗푖 =⎧⎪⎨⎪⎩1, if 푖 = 푘 and 푝 = 푎′−1, if 푖 = 푘 and 푞 = 퐿0, otherwise,∀푖 ∈ 0,… , 푚 − 1, ∀퐸푝푞 ∈ 푛푚퐿 , ∀푘 = 0,… , 푚 − 1. (4.7)The 푘th path is defined to begin on vertex 푘.Each of the 푚 copies of 푛푚퐿 have identical edge weights. The optimal solutionfor the shortest path problem for each of the 푚 paths will therefore be the same as ifthey were solved on a single 푛푚퐿 . However, the third index 푘 allows us to maintaincommunication information (Figure 4.3).Figure 4.3: The same solution as Figure 4.2, but modelled on four copies of 44:0,1,2, and 3. All paths are well-defined.4.2.2 CapacityThough the 푚 copies of 푛푚퐿 technically give us disjoint paths, they are notdisjoint in the original 푛푚퐿 (Figure 4.2). To ensure disjointedness, we introduce thecapacity constraint, which limits each edge to be used at most once throughout all푚 copies of 푛푚퐿푚−1∑푘=0푥푘 푝푞푖푗 ≤ 1, ∀푖, 푗 ∈ {0,… , 푚 − 1}, ∀퐸푝푞 ∈ 푛푚퐿 . (4.8)604.2. The 3C Constraints of Assignment Feasibility4.2.3 ContiguityFinally, we generalize 푥푘 푝푞푖푗 to 푥푘 푝푞푟 푖푗 so as to tie together all joined cycle stacksin 핋 . Let 푟 and 푠 be any two cycle stacks in 핋 which share common set  ofedge stacks28. Then the shared edge flows (assignments) are the same if푥푘 푝푞푟 푖푗 = 푥푘 푝푞푠 푖푗 = 푥푝푞푖푗 , ∀푖, 푗, 푘 ∈ {0, 1,… , |퐸푝푞|}, ∀퐸푝푞 ∈  . (4.9)4.2.4 Asinglular LP Problem StatementCombining the 3C constraints yields the following general LP for finding theminimally weighted feasible assignment for any 픾̊min∑푤푝푞푖푗 푥푝푞푖푗 (4.10)s.t.|퐸푝푞−1|∑푗=0푥푘 푝푞푟 푖푗 −|퐸푝푞−1|∑푗=0푥푘 푞푝푟 푗푖 =⎧⎪⎨⎪⎩1, if 푖 = 푘 and 푝 = 푎′−1, if 푖 = 푘 and 푞 = 퐿0, otherwise, (4.11)∀ 푖, 푘 ∈ {0, 1,… , |퐸푝푞|}, ∀ 퐸푝푞 ∈ 푟,∀푟 ∈ 핋 (4.12)|퐸푝푞−1|∑푘=0푥푘 푝푞푟 푖푗 ≤ 1,∀ 푖, 푗 ∈ {0, 1,… , |퐸푝푞|}, ∀ 퐸푝푞 ∈ 푟,∀푟 ∈ 핋 (4.13)푥푘 푝푞푟 푖푗 = 푥푘 푝푞푠 푖푗 = 푥푝푞푖푗 ,∀ 푖, 푗, 푘 ∈ {0, 1,… , |퐸푝푞|}, ∀ 푟,푠 ∈ 핋 ,∀퐸푝푞 ∈ 푟 and 푠 (4.14)푥푝푞푖푗 ∈ {0, 1}. (4.15)The LP does not account for fully or partially constrained path stacks.The 3C constraints are sufficient conditions to ensure that any feasible solutionto the LP is also an assignment on 픾.Theorem 4.2 (3퐶 Constraints Produce Feasible 퐴(픾̊)). The 3퐶 constraints definea system of linear constraints which produce feasible assignments on any 픾̊.28i.e. They’re ‘joined’ in the sense of Lemmas 2.26 and 2.27.614.2. The 3C Constraints of Assignment FeasibilityProof. The communication constraint produces 푚 paths on 푛푚퐿 , where each path푖 starts on 푣푎′푖 and ends on 푣퐿푖 . The capacity constraint ensures that the paths aredisjoint. That an assignment is produced on each 퐸푝푞 is clear as |퐸푝푞| = 푚, thereare 푚 edges in 퐸푝푞 with non-zero flow values, and those edges are all disjoint.This implies a one-to-one, onto mapping from the vertices 푉푝 to those of 푉푞. Thisis the definition of an asingular edge stack assignment (Definition 2.15). Thus,communication and capacity produce assignments on 퐶푛푚퐿 . By the construction oflinear cycle stacks (Definition 4.1), this implies that each path is a cycle in 푛푚. ByCorollary 2.20 and the construction of 푛푚퐿 , the disjoint paths in 푛푚퐿 cycles form adisjoint cover cycle of 퐶푛푚. As the disjoint cover cycle is also an assignment, theassignment is feasible by Theorem 2.23.The contiguity constraint ensures that joined asingular cycle stacks have thesame assignments on shared edge stacks. By Lemmas 2.26 and 2.27, joinednesspreserves feasibility. Therefore, the 3퐶 constraints define linear constraints whichproduce feasible assignments on any 픾̊.The above LP for 퐴(픾̊) is a form of restricted regional optimization, applyingonly to cyclic edge stacks (Definition 2.12). There is no need to apply it to theentirety of 픾̊ as the same optimal feasible assignment can be found by restricting itto each푖 ∈ 픾.4.2.5 Size Complexity of Asingular LPOur LP introduces a large number of additional edges. Linearisation of cyclestacks adds at most |핋| edge stacks while communication constraints require atmost푚 = max{||| ∈ 핋} (4.16)copies of  , yielding a total of푚(|| + |핋|) (4.17)edge stacks. Capacity constraints do not add additional edge stacks, though conti-guity constraints introduce at most |핋| additional copies of  , since it’s possiblefor an edge stack 퐸푝푞 ∈  to occur in every 푖 ∈ 핋 (Figure 4.4). Finally, thelargest edge stack in 픾̊ is also 푚. The size complexity 푉퐿푃 , in terms of numberof vertices, required to create the graph necessary to model our LP for some 픾̊ is624.2. The 3C Constraints of Assignment Feasibility(a) (b)Figure 4.4: (a) Spanning tree 핋픾 produces two fundamental cycle stacks (b) 0 and1, both containing 퐸02.therefore bounded above by푉퐿푃 ≤  (푚2(|핋| + 푚)(|| + |핋|)) (4.18)=  (푚2(|핋||| + |핋|2 + 푚|| + 푚|핋|)) (4.19)≤  (푚2(||2 + ||2 + 푚|| + 푚||)) (4.20)=  (푚2||2 + 푚3||) (4.21)≤  (푚2||4 + 푚3||2) (4.22)≤  (푚3||4) . (4.23)The replacement of |핋| with || in Equation 4.20 is made as at most every edgestack is restricted29. The replacement in Equation 4.22 follows from the fact thatthe number of edge stacks are bound by | |2, just as the number of edges in asimple graph are bound by the square of the number of vertices30.We can therefore model the assignment problem for 픾̊ with size complexity of (푚3||4). In the case of nucleic acid phosphate backbones, we’ll see that푚 ≤ 16or infinite, so that the constant factor is at most 256. As stacked graphs have onlybeen defined for the finite case, infinite values of 푚 are ignored.29Every edge stack is restricted if every edge stack forms a loop stack. In this case, however, thereis no optimization problem in light of Lemma 2.3730There are at most (푁2) edges in a simple graph consisting of푁 vertices, with((푁2))= (푁(푁 − 2)2)=  (푁2) . (4.24)634.3. Modelling Singular Constraints: ULA4.3 Modelling Singular Constraints: ULAThe only non-basic constraint we’ve considered is ULA (Definition 2.42). It’sa fortunate consequence of our construction of the contiguity constraint that theindex 푘, which indicates the copy number of a cycle stack 푛푚, also represents thelayer number (Theorem 2.32) for the region to which 푛푚 belongs. Equation 4.9forces shared edge stacks for two joined cycle stacks to have the same flow valuefor the same copy 푘; contiguity is defined on copies of cycle stacks, not the stacksthemselves. Thus, all connected edges in 퐴(픾̊) have the same copy index 푘 if theybelong to the same region. Since the flow value is the same for 푘 for a given regionregardless of the cycle stack number 푠, the index can be dropped to produce푥푘 푝푞푖푗 .Once 퐴(픾̊) has been found, we no longer need the cycle stack copies created to forthe communication constraint.Modelling ULA constraints as an LP requires us to formulate constraints as bi-nary logical ones. Casting techniques are from Discrete Optimization course notes.If a vertex is in layer 푘 of푟, then it’s incident on one or two edges, otherwiseit’s incident on none31.|푟|−1∑푗=0푥푘 푝푞푖푗 +|푟|−1∑푗=0푥푘 푞푝푗푖 ∈ {0, 1, 2}, ∀푘 = 0,… , |푟| − 1,∀퐸푝푞 ∈ 푟 (4.25)We next cast Equation 4.25 into binary form so that its solution is either 0 or 1.The constraints for the layer indicator value 푦푘 푝푖 of 푣푝푖 ∈ 푟푘 are0 ≤ 푦푘 푝푖 ≤ 1 (4.26)푦푘 푝푖 ≤|푟|−1∑푗=0푥푘 푝푞푖푗 +|푟|−1∑푗=0푥푘 푞푝푗푖 (4.27)|푟|−1∑푗=0푥푘 푝푞푖푗 +|푟|−1∑푗=0푥푘 푞푝푗푖 ≤ 2 ⋅ 푦푘 푝푖 (4.28)where the summation conditions are those of Equation 4.25. Replacing the sum-mations with 1 or 2 forces 푦푘 푝푖 = 1 while a value of 0 forces 푦푘 푝푖 = 0.We also want to know whether two layers푟푎 and푡푏 from adjacent regions푟and푡 (Definition 2.11) are themselves adjacent through퐴푝푞 for a given퐸푝푞 ∈ ̉푟푡.31Recall that cycle stacks are in linear form, hence the existence of vertices incident on only singleedges in a path.644.3. Modelling Singular Constraints: ULAFirst, we create a new variable that indicates when 푦푎 푝푖 and 푦푏 푞푗 are simultaneouslytrue푦푎푏 푝푞푖푗 ∶= 푦푎 푝푖 ∧ 푦푏 푞푗 (4.29)with constraints− 푦푎 푝푖 + 푦푎푏 푝푞푖푗 ≤ 0 (4.30)− 푦푏 푞푗 + 푦푎푏 푝푞푖푗 ≤ 0 (4.31)푦푎 푝푖 + 푦푏 푞푗 − 푦푎푏 푝푞푖푗 ≤ 1. (4.32)When both 푦푎 푝푖 = 푦푏 푞푗 = 1, 푦푎푏 푝푞푖푗 = 1. Otherwise, 푦푎푏 푝푞푖푗 = 0. Next, we note that푦푎푏 푝푞푖푗 ⋅ 푥푝푞푖푗 = 1 (4.33)precisely when 푣푝푖 is incident on 푣푞푗 under 퐴푝푞, h(푣푝푖 ) = 푎, and h(푣푞푗 ) = 푏. Equation4.33 therefore indicates whether 푟푎 is incident on 푡푏 through 퐴푝푞.The definition of ULA requires that all vertices in 푟푎 that are adjacent on 푡are all adjacent on the same 푡푏. Since there are |̉푟푡| edge stacks between 푟 and푡, it follows that∑퐸푝푞∈̉푟푡|푉푝|−1∑푖=0|푉푞|−1∑푗=0푦푎푏 푝푞푖푗 ⋅푥푝푞푖푗 ∈ {0, |̉푟푡|}, ∀푎 ∈ 0,… , |푟|−1, 푏 ∈ 0,… , |푡|−1.(4.34)As the equation is non-liner, each product푦푎푏 푝푞푖푗 ⋅ 푥푝푞푖푗must be replaced with an indicator value similar to Equation 4.29. Letℎ푎푏 푝푞푖푗 ∶= 푦푎푏 푝푞푖푗 ∧ 푥푝푞푖푗 (4.35)with constraints− 푦푎푏 푝푞푖푗 + ℎ푎푏 푝푞푖푗 ≤ 0 (4.36)−푥푖푗 + ℎ푎푏 푝푞푖푗 ≤ 0 (4.37)푦푎푏 푝푞푖푗 + 푥푝푞푖푗 − ℎ푎푏 푝푞푖푗 ≤ 1 (4.38)so that Equation 4.34 can be written as∑퐸푝푞∈̉푟푡|푉푝|−1∑푖=0|푉푞|−1∑푗=0ℎ푎푏 푝푞푖푗 ∈ {0, |̉푟푡|}, ∀푎 ∈ 0,… , |푟| − 1, 푏 ∈ 0,… , |푡| − 1.(4.39)654.3. Modelling Singular Constraints: ULAAs |̉푟푡| is fixed, Equation 4.39 can be normalized to∑퐸푝푞∈̉푟푡|푉푝|−1∑푖=0|푉푞|−1∑푗=01|̉푟푡| ℎ푎푏 푝푞푖푗 ∈ {0, 1}, ∀푎 ∈ 0,… , |푟| − 1, 푏 ∈ 0,… , |푡| − 1.(4.40)Let ℎ푟푡푎푏 be the summation in Equation 4.40 for given 푎 and 푏 so thatℎ푟푡푎푏 = {0, 1}. (4.41)The variable ℎ푟푡푎푏 is the layer adjacency indicator, with ℎ푟푡푎푏 = 1 if 푟푎 and 푠푏are mutually uniformly adjacent, and 푤푟푡푎푏 = 0 if 푟푎 and 푡푏 are completely andmutually non-adjacent.Equations 4.25 to 4.41 define the ULA non-basic singularity constraint for ev-ery pair of regions 푟 and 푡 with a non-empty boundary ̉푟푡 in 퐴(픾), where ℎ푟푡푎푏indicates when two layers푟푎 and푡푏 are uniformly adjacent to each other. We shallnot conduct an analysis ULA’s space complexity.It’s possible to reduce the number of ULA constraints. Equation 4.34 becomesnon-linear if 퐴(픾̊) is solved for first prior to enforcing ULA on 퐴(픾̉). The term푦푎푏 푝푞푖푗 becomes a fixed binary value as the layers to which 푣푝푖 ∈ 푟 and 푣푞푗 ∈ 푠are are explicitly solved for in 퐴(픾̊). Equations 4.35 through 4.38 can be removed.In general, however, we cannot solve for 퐴(픾̃), 퐴(픾̊), and 퐴(픾̉) independently andassume the resulting global solution퐴(픾) is optimal. Figure 4.5 illustrates this witha simple mixed 픾. Whether or not optimal 퐴(픾) is solved for globally or throughlocal iterations (Section 4.1) will depend on the number of vertices and edges of퐺 as well as whether 퐴(픾) must be optimal or only reasonably so.This ends our discussion of stacked graphs. In the following chapters we turnto the structure of RNA and the process of writing the conformation problem as anoptimal feasible assignment on stacked graphs.664.3. Modelling Singular Constraints: ULA(a) (b)(c)Figure 4.5: (a) Weighted 픾 defined by mixed 3 with asingular 퐸01 and singular퐸12 and 퐸20. (b) The optimal assignment on 퐸01 (solid lines) has a weight of 0.However, all assignments on 퐸12 and 퐸20 must consist of forms similar to those indashed lines in order to satisfy ULA. In each case, the total weight of 퐴12 and 퐴20is always 30. In (c), however, 퐴01 has a weight of 2 while 퐴12 and 퐴20 total to 0.Thus optimization over 퐴(픾̃) first yields a different solution than optimizing over퐴(픾̉) first.67Chapter 5Kinematic ChainsKinematic chains are mathematical models of rigid objects interconnected byjoints, or ‘lower pairs’, that allow for a variety of relativemotions. Their primary ap-plication is in mechanical engineering, particularly robotics. They can, however, beused to model chemical molecules by treating bonds as rigid structures and atomicrotation about bonds as rotational joints.The literature on kinematic chains is vast and deep. The aim of this chapteris simply to introduce their general structure and demonstrate how RNA can bemodelled as one, including only those concepts relevant to our project.The following discussion is based heavily on [Ang07] and [McC90]. The termchain will be used as a shorthand for ‘kinematic chain’ throughout the remainderof this work.5.1 Denavit-Hartenberg ParametersKinematic chains are defined primarily by the details of their joints. A pris-matic pair, 푃 , produces translational motion between successive reference frames퐹푖 and 퐹푖+1 (Figure 5.1(a)) while a rotational pair, 푅, provides a rotational trans-formation (Figure 5.1(b)). Composition of pairs produces both translational androtational transformations between frames 퐹푖 and 퐹푖+2 (Figure 5.1(c)). The rigidcomponents being modelled are implied by the relative location and orientation ofadjacent reference frames. The composite chain in Figure 5.1(c) is termed a PRchain while its sub-chains are P and R chains, respectively. In general, chains arenamed after ordered, serial sequence of their joints, with repeated sub-sequencesreplaced by a numeric value. Thus, a chain formed by three prismatic joints fol-lowed by a single rotational joint is a 푃푃푃푅 chain, or a 3푃푅 chain. The last frameof reference in a chain is commonly termed the end-effector and will, in this work,be denoted by a red circle.There are a number of other joint types, such as helical and spherical, howeverall can be reduced to combinations of prismatic and rotational [Ang07]. In addition,non-serial or parallel chains are possible (Figure 5.2).Another categorization relates to the space in which the chain exists. Planar685.1. Denavit-Hartenberg Parameters(a) Prismatic Pair (b) Rotational Pair (c) PR ChainFigure 5.1: The two fundamental kinematic pairs: (a) prismatic, 푃 , and (b) rota-tional, 푅. 푃 pairs produce translational motion while 푅 pairs produce rotationalmotion, with each providing a single degree of freedom. Their composition (c) re-sults in a PR chain, which has two degrees of freedom. The end-effector is indicatedin red.chains are where the entire range of motion for the end-effector exists in a plane,while for spherical chains it exists on a sphere. Spatial chains have no such restric-tions. Finally, open chains are those wherein the end-effector is free to move, whilein closed chains the final reference frame is fixed [McC90].In our study of RNA, we will concern ourselves solely with 6푅, serial, spatialopen chains. However, we will have recourse to 2푅 and 3푅 chains to illustratecertain concepts due to the ease in visualizing their motions.There are a variety of mathematical treatments for chains, including the use ofquaternions and screws [McC90]. The most common approach involves standardmatrix transforms, which is what we shall use here as the particular notation is oflittle consequence to us and matrices are more widely known.Matrix representations of lower pairs are constructed usingDenavit-Hartenbergparameters. In the context of purely rotational chains, the parameters are definedas follows [Ang07]:− 푎푖, the distance between the primary axis, 푍푖, of joints 푖 and (푖 + 1)− 훼푖, the angle or twist between the primary axis of joints 푖 and (푖 + 1)− 푏푖, the 푍푖-coordinate or offset between the intersection of 푍푖 and 푋푖+1695.1. Denavit-Hartenberg ParametersFigure 5.2: An example of a complex parallel kinematic chain with six ‘legs’[Ang07].− 휃푖, variable torsion angle about the 푥-axis of rotational joint 푖, with respectto positive 푍푖.Figure 5.3 illustrates the parameters for a 6푅 spatial chain.The matrix formation of the 푖th rotational pair is푄푖(휃푖) =⎡⎢⎢⎢⎣cos 휃푖 −cos 훼푖 sin 휃푖 sin 훼푖 sin 휃푖 푎푖 cos 휃푖sin 휃푖 cos 훼푖 cos 휃푖 − sin 훼푖 cos 휃푖 푎푖 sin 휃푖0 sin 훼푖 cos 훼푖 푏푖0 0 0 1⎤⎥⎥⎥⎦ . (5.1)Each set of parameter values defines a unique pair. Composition of pairs isaccomplished via the production of transformation matrices. In the case of a 6푅chain, we have푄 ∶= 푄1푄2푄3푄4푄5푄6, (5.2)where 푄 encodes the position and orientation of the final reference frame 퐹6 (i.e.the end-effector) with respect to the base frame, 퐹032. 푄, being the product of sixsingle-variable functions, can be treated as a single six-variable function푄(휃) ∶= 푄(휃1, 휃2, 휃3, 휃4, 휃5, 휃6). (5.3)32This explains why variable indexing begins at 1 and not 0.705.1. Denavit-Hartenberg ParametersFigure 5.3: The Denavit-Hartenberg parameters associated with a 6푅 chain. Miss-ing are the twist angles. In the case of 훼3, this would be the angle between rotationalaxes 푍3 and 푍4. From [Ang07].Every chain has an associated workspace which describes the locations andorientations reachable by its end-effector [Ang07]. Like a human arm, ‘mathemat-ical arms’ have limited mobility. As we have difficulties touching the point of ourbacks between the shoulder blades, kinematic chains have difficulties touching por-tions of space around them. The 3푅 in Figure 5.4(a), for example, cannot place itsend-effector immediately above or below the base reference fame, indicated by theorigin.However, like human arms, some locations of space are easier to reach thanothers. There are multiple sets of angles for shoulder, elbow, and wrist joints thatplace our hands in front of our face with a given orientation. So too with kinematicchains. The workplace of a chain is divided into distinct regions. All end-effectorpositions, which are encoded in 푄, that lay within a given region have the samenumber of torsion solutions휃 ∶= ⟨휃1, 휃2, 휃3, 휃4, 휃5, 휃6⟩ (5.4)that produce their respective 푄.For example, the 3푅 chain workspace in Figure 5.4(b) is divided into 2 regions.There exist two sets of torsion angles 휃 = ⟨휃1, 휃2, 휃3⟩ and 휃′ = ⟨휃′1, 휃′2, 휃′3⟩ thatwould place the end-effector anywhere within the outer region, while four exist forthe central region.715.2. Forward and Inverse Kinematics(a) (b)Figure 5.4: (a) A 3푅 chain and (b) its workspace. The shaded sections of the work-place indicate different regions. From [Ang07].5.2 Forward and Inverse KinematicsThere are two general problems associated with kinematic chains, termed theforward and inverse kinematic problems, or FK and IK. In the context of 6푅 chains,FK asks: ‘Given a set of torsion angles 휃 =< 휃1,… , 휃6 >, what is 푄?’33. Thesolution is trivial - evaluate 푄 at 휃.The inverse problem asks: ‘Given 푄, what is the set of all 휃 that produce 푄?’.This question, like other inverse problems, has an exceptionally non-trivial answer.Fortunately, for our 6푅 case, general solutions do exist. For 6푅 chains, thereexist either a) at most 16 solutions or b) infinite solutions to the IK problem for agiven 푄 [Ang07]. Figures 5.5(a) and 5.5(b) give an example of finite and infinitesolutions, respectively.The workspace of any chain is a subspace of ℝ3 × [0◦, 360◦)3. The real com-ponents ℝ reflect the three Cartesian coordinates of the end-effector while the an-gular components [0◦, 360◦) represent the three Euler angles associated with theend-effector’s orientation. These will be referred to as the cartesian and euleriancomponents of a workspace, respectively, and collectively as the workspace.The torsional space of a 6푅 chain is [0◦, 360◦)6, and is the range of values that휃 can take. 푄 is a many-to-one function from torsion space to workspace푄 ∶ [0◦, 360◦)6 → ℝ3 × [0◦, 360◦)3. (5.5)33i.e. ‘What is the location and orientation of 퐹6 with respect to 퐹0?’725.3. Kinematic Nucleic Acids(a) (b)Figure 5.5: There are two solutions to the IK problem for (a) the 3푅 chain at푄 (redcircle): 푠00 with 휃 = ⟨135◦, 90◦, 135◦⟩ and 푠01 with 휃′ = ⟨45◦, 270◦, 135◦⟩. Infinitesolutions exist for (b) the 2푅 chain at푄 if both joints rotate at equal rates in oppositedirections. In contrast with (a) where joint rotation axes are perpendicular to thepage, the joints of (b) are vertically parallel to the page.The FK problem can therefore be stated as finding the image of 푥 ∈ [0◦, 360◦)6under푄, while the IK problem involves finding the pre-image of 푦 ∈ ℝ3×[0◦, 360◦)3under푄. The image of the entirety of [0◦, 360◦)6 under푄 is the conformation spaceassociated with푄, or a particular parametrization of a 6푅 chain. There exist fast al-gorithms to calculate all 6푅 chain IK solutions for any single 푦 ∈ ℝ3 × [0◦, 360◦)3[MC94], a fact we’ll use in the next chapter. However, no such algorithms existto find the entire pre-image of a conformation space, which is what we wish toapproximate (see Chapter 1).Conformation spaces encapsulate how motion in [0◦, 360◦)6 is reflected, under푄, inℝ3×[0◦, 360◦)3. It is not a synonym for workspace, as workspaces are essen-tially volumes of space in ℝ3 × [0◦, 360◦)3 and it’s possible for two different chainsto have the same workspace.5.3 Kinematic Nucleic AcidsConverting a phosphate backbone into a kinematic chain is straightforward. Letthe atoms, bond angles, bond lengths, and torsion - or dihedral - angles of the back-bone be, respectively,735.3. Kinematic Nucleic Acids퐴푡표푚 ∶=⟨푃5, 푂5, 퐶5, 퐶4, 퐶3, 푂3, 푃3⟩퐴푛푔푙푒 ∶=⟨180◦, 180◦, 푃5 − 푂5 − 퐶5, 푂5 − 퐶5 − 퐶4, 퐶5 − 퐶4 − 퐶3,퐶4 − 퐶3 − 푂3, 퐶3 − 푂3 − 푃⟩퐵표푛푑 ∶=⟨0, 푃5 − 푂5, 푂5 − 퐶5, 퐶5 − 퐶4, 퐶4 − 퐶3, 퐶3 − 푂3, 푂3 − 푃3⟩푇 표푟푠 ∶=⟨0, 훼, 훽, 훾, 휎, 휖, 휁⟩ (5.6)where each element of퐴푛푔푙푒 and퐵표푛푑 is the angle between three successive atomsabout their interior bonds and distance between two successive bonds, respectively(Figure 5.6).Figure 5.6: Atoms of the phosphate backbone. Atomic bond angles are indicatedby thin black arrows and torsion angles are indicated by thick blue arrows. Notethat there is no offset between successive atoms. Hydrogen atoms are excluded, butcan be incorporated with some modifications.Accordingly, frame 퐹푖 about atom 퐴푡표푚[푖] is defined by푎푖 = 퐵표푛푑[푖]훼푖 = 퐴푛푔푙푒[푖] − 180◦휃푖 = 푇 표푟푠[푖]푏푖 = 0, (5.7)providing a parametrization of Equation (5.1). Index 0 orients the base frame aboutthe 푃5 atom and is technically not needed (see Equation 5.2). It is included for com-pleteness’ sake. For our RNA chain,푄 defines the relative position and orientationof the two phosphate atoms, 푃 5 and 푃3, in the backbone.745.4. Outline of Converting IK Solutions and Stacked Graphs5.4 Outline of Converting IK Solutions and StackedGraphsThe following chapter details the technique we’ll use to sample the conforma-tion space for kinematic chains, in general, and single phosphate backbones, in thespecific. This sample set will, in Chapter 7, be converted into a stacked graph 픾,feasible assignments on which are point-wise approximation of the space’s struc-ture, as described in Section 2.1. Figure 5.7 illustrates the general process.755.4. Outline of Converting IK Solutions and Stacked Graphs(a) (b)(c) (d)Figure 5.7: (a) A lattice is projected onto a chain workspace  , after which (b)IK solutions are found at each lattice vertex. (c) Vertex stacks are formed from thesolutions and edge stacks created between samples adjacent on the lattice with thenumber of solutions at each location defining regions and boundaries (dotted lines)for a stacked graph 픾. Finally, (d) an optimal feasible assignment 퐴 is found for 픾using the LP described in Chapter 4.76Chapter 6Conformation Space SamplingIn this chapter we describe the process by which chain conformation spaces aresampled, including a limited analysis of the number of samples that will be neededfor the case of phosphate backbones. The first section introduces the techniquewhile the second formally defines terms.6.1 Sampling TechniqueAs noted in Section 5.2, every 6R chain workspace is a subspace of ℝ3 ×[0, 360◦)3. The extent of the ℝ3 (cartesian) components, or the maximum distancethat can be had between the 푃5 and 푃3 atoms, are determined by the bond lengths푎푖 and angles 훼푖 of the chain and are therefore dependent on specific parametriza-tions. Large values of 푎푖 and values of 훼푖 close to 180◦ tend to produce subspacesofℝ3 with a greater maximal extent than smaller 푎푖 and more acute 훼푖 (Figure 6.1).This is a basic geometric result. Eulerian component extent is affected by chainparametrization to a lesser degree, given that the super-space [0, 360◦)3 is of finiteextent.Ideally, a sampling lattice bounds the workspace as tightly as possible as wewish to sample the workplace exterior as infrequently as we can (i.e. the 0 so-lutions in Figure 5.7(b)). However, we would also like a lattice that can be usedirrespective of chain parametrization, and therefore of workspace shape. To thisend, we normalize all workspaces by dividing each 푎푖 lengths by the maximal ex-tent of the workspace. This produces normalized workspaces with maximal extentsof 1, fitting nicely into the cubic space [−1, 1]3 when our base frame 퐹0 (i.e. atom푃 5) is located at the origin < 0, 0, 0 > (Figure 6.2).Determining maximal workspace extents will not be covered here. For purerotational chains with no offset (see Section 5.1), such as the phosphate backbone6푅 chain, maximal extents are derivable by trigonometric arguments. Figure 5.6illustrates a backbone conformation with maximal extent.Sampling itself is done via bisection, repeatedly halving the [−1, 1] and [0, 360◦)lattice components and taking samples on the resultant grid. We denote the numberof bisections for the 푖th cartesian interval to be 푛푐푖 . The number of sample points776.1. Sampling Technique(a) (b)Figure 6.1: Planar 2푅 example of how small changes in parameter values (휃 → 휃′)can impact maximumworkspace extent (푑 → 푑′). Only the cartesian componentsof the workspaces (pink annuli) are shown.on the 푖th interval (including the ±1 ends of the interval) is 2푛푐푖 +1, so that the totalnumber for the entire cartesian component is(2푛푐1 + 1)(2푛푐2 + 1)(2푛푐3 + 1). (6.1)Similarly, the number of eulerian samplings, defined by the number of bisections푛푒푖 , is(2푛푒1 )(2푛푒2 )(2푛푒3 ) (6.2)with the +1 dropped due to the the circularity of [0, 360◦).While each 푛푐푖 and 푛푒푗 are allowed to be different, to simplify matters, we’llassume that each 푛푐푖 take on the same value, as well as each 푛푒푗 . This allow us torefer to 푛푐 and 푛푒 without the additional subscripts. The total number of samplesfor a lattice becomes(2푛푐 + 1)3(2푛푒)3 ≈ 23(푛푐+푛푒) = 8푛푐+푛푒 . (6.3)For small values, the number of samples is rather large: at 푛푐 = 푛푒 = 4, wehave 16.7 million samples, and at 푛푐 = 푛푒 = 5, a little over a billion. These figuresare for samples, not solutions, the later of which are bound by a constant푘8푛푐+푛푒 (6.4)786.1. Sampling TechniqueFigure 6.2: Normalizing workspaces A and B allows the same sampling lattice tobe used.with 푘 <= 16. Recall from Section 5.2 that 6푅 chains have at most 16 IK solutionsin the finite case.But how accurately do four bisections approximate the underlying space? Whatof five bisections? Can we get away with ‘only’ a billion samples? Fortunately,there is a practical upper limit on the values of 푛푐 and 푛푒 resulting from the accuracyof current RNA crystallography data.The Nucleic Acid Database (NDB) is a primary repository for nucleic acid in-formation. The standard structural geometries of nucleic acids used by the NDB[Dat16] - including bond lengths and angles - are those of [GSC+96]. Table 6.1displays the standard bond lengths, from which we can determine that the maximalextent of any unnormalized kinematic RNA workspace is, at most, 9.141 Å, a grossoverestimation given that it supposes all bond angles are 180◦.Minimum bond length error is approximately 0.001Å. Any sampling lattice796.1. Sampling Techniqueassociated with the workspace of maximal possible extent with an (unnormalized)grid size less than 0.001Åwould thus provide a sampling resolution below the errorbounds. This in turn provides us a practical upper limit on the value of 푛푐 .Table 6.1: RNA phosphate backbone mean bond lengths (푥̄) in Angstroms (Å),including their standard deviations (esd), number of samples (N), standard errors(se), and upper bounds of the mean lengths within two standard deviations. Totallengths indicate maximum possible extent of workspace, where all bond angles areassumed 180◦. * from [GSC+96].Bond LengthsBond 푥̄∗ esd∗ N∗ se 푥̄ + 2seP-O5 1.593 0.010 15 0.003 1.599O5-C5 1.440 0.016 14 0.004 1.448C5-C4 1.510 0.013 80 0.001 1.512C4-C3 1.524 0.011 80 0.001 1.526C3-O3 1.433 0.019 13 0.005 1.443P-O3 1.607 0.012 13 0.003 1.613Total Length 9.107 - - - 9.141The value of 푛푒 is easier to restrict, since it’s parameter - and thereforeworkspace- independent. From Table 6.2, we see that the smallest standard error for phosphatebackbone bond angles is roughly 0.2◦.Table 6.2: RNA phosphate backbone mean bond angles (푥̄) in degrees, includingtheir standard deviations (esd), number of samples (N), and standard errors (se). *from 4.5[GSC+96].Bond AnglesAngle 푥̄∗ esd∗ N∗ seP-O5-C5 120.9 1.6 15 0.4O5-C5-C4 109.4 0.8 14 0.2C5-C4-C3 115.5 1.5 80 0.2C4-C3-O3 110.6 2.6 80 0.3C3-O3-P 119.7 1.2 13 0.3The effect of bisections on grid lengths - including the maximal and normalizedcartesian lengths - is described in Table 6.3. At 푛푐 = 14 and 푛푒 = 12 bisections,sampling resolutions is below 0.001Å and 0.2◦, respectively.806.1. Sampling TechniqueTable 6.3: Effect of the number of bisections on the mean, maximal, and normal-ized cartesian grid lengths (Å), as well as the angular eulerian grid lengths (de-grees). Bold values indicate cut-off points where lengths fall below standard errorof existing experimental data.# Bisects Mean Maximal Normalized Angular0 9.107 9.141 1 3601 4.554 4.570 0.5 1802 2.277 2.285 0.25 903 1.138 1.143 0.125 454 0.569 0.571 0.0625 22.55 0.284 0.286 0.03125 11.36 0.142 0.143 0.01563 5.67 0.071 0.071 0.00781 2.88 0.035 0.036 0.00391 1.49 0.018 0.018 0.00195 0.710 0.009 0.009 0.00098 0.411 0.004 0.004 0.00049 0.212 0.002 0.002 0.00024 <0.113 0.001 0.001 0.00012 < 0.114 <0.001 <0.001 0.00006 < 0.1816.2. Formal DefinitionsIt is important to note that the distances associated with these values of 푛푐 and푛푒 are not indicative of actual crystallographic resolutions, but the errors associatedwith means. Some of the best existing data has a resolution of 0.48Å with values< 1Å being considered highly accurate [BHA15]. 푛푐 = 5 therefore provides ahigher resolution than most, if not all, existing data.Calculating a more realistic limit for 푛푒 is difficult. For our purposes, we’ll take푛푒 = 7, equivalent to 2.8◦, to be a reasonable upper limit.This equates to 85+7 ≈ 69 billion sample points. Even in light of the existenceof high-speed IK algorithms, sampling the space is somewhat problematic: at asolving rate of (at least) 10 ms per sample [MC94], a total of 7,986 days - or 22years - of CPU time is needed. Samples, however, are independent, so that thesolving process is trivially parallelizable and therefore a candidate for distributed,cloud, or supercomputing.Fortunately, wemay need significantly fewer than 70 billion samples. The semi-rigid nature of backbone chains means that the accuracy of a conformation spaceapproximated by any single chain parametrization may be quite low, depending onthe value distributions on the parameters. It is therefore not necessary to obtain alarge number of samples. What is important is how conformation spaces changeunder a distribution of parametrizations, changes which may manifest at low sam-pling resolutions (i.e. small values of 푛푐 and 푛푒). Chapter 8 covers techniques foranalysing such changes.6.2 Formal DefinitionsTo be consistent across RNA chain parametrizations as well as 푛푐 and 푛푒 val-ues, sample points require unambiguous labels. Using lattice coordinates alone isinsufficient. For one, there are two lattices: the normalized lattice, with rationalcartesian coordinates in [−1, 1], and the lattice corresponding to the actual, unnor-malized workspace, with real cartesian coordinates. For another, coordinates withreal or rational values are awkward to work with in algorithmic contexts, whereiterating over integers is common place.There is also the issue of comprehension. If normalized coordinates are treatedas canonical sample names, what, for instance, is the relationship between samples푆푎 and 푆푏 below?푆푎 ∶⟨−12, 12.34, 45◦, 270◦, 180◦⟩(6.5)푆푏 ∶⟨−34, 14, 0, 180◦, 90◦, 225◦⟩(6.6)Are they close to each other on the lattice relative to their sampling resolutions,826.2. Formal Definitionsor quite distant? Do they even exist in the same set of resolutions, or is each vec-tor component from different 푛푐 and 푛푒 values34? This isn’t clear from the vectorsalone, and knowing whether samples are adjacent to each other on a lattice is im-portant.We address these problems by introducing a formal sample naming scheme,followed by a set of functions that allow us tomove between normal and non-normallattices and alternative labelling techniques which will prove useful. First, samplenaming.We’ll begin with the one dimensional case, where each sample is either on[−1, 1] or [0, 360◦), then generalize to samples on [−1, 1]3 × [0, 360◦)3.At 푛푐 = 0, there are only two samples, located at −1 and +1 (Figure 6.3). Wedefine these as 푆0 and 푆1, respectively. Increasing to 푛푐 = 1 yields a third sample,푆2. At 푛푐 = 2, 푆3 and 푆4 appear. The process continues, labelling new samples atsuccessive midpoints, starting from the −1 end and working towards +1, namingthem by increasing integer subscripts.Figure 6.3: Sample labelling on cartesian components up to 푛푐 = 3 bisections.Successive lines indicate sample labels introduced at particular 푛푐 values (in red)as well as previously generated samples (in black). The bottom axis indicates thecoordinate value of each sample in the normalized sample space.Definition 6.1 (Bisectors). The 푖th cartesian and 푗th eulerian bisectors are 푛푐푖 and푛푒푗 , respectively. The integers generated by 푛푐푖 and 푛푒푗 fall in distinct ranges (Table6.4).34For example, 푆푎[1] = − 12 and 푆푏[1] = − 34 are produced by 푛푐 = 2 and 3, respectively.836.2. Formal DefinitionsThe values in Table 6.4 result from the following theorem.Theorem 6.2 (Resolution). Let 푘 > 1 and 푘′ > 1 be generated by 푛푐 and 푛푒,respectively. Then푘 ∈ [2푛푐−1 + 1, 2푛푐 ] (6.7)푘′ ∈ [2푛푒−1, 2푛푒 − 1] (6.8)and푛푐 = ⌈log2 푘⌉ (6.9)푛푒 = ⌊log2 푘′ + 1⌋. (6.10)In this context, bisectors 푛푐 and 푛푒 are the resolutions of 푘 and 푘′, respectively.Proof. The first part can be proved via induction on Figure 6.3 for 푛푐 and a similarfigure for 푛푒. For the second part, from Equation 6.9 we have2푛푐−1 + 1 ≤ 푘 ≤ 2푛푐2푛푐−1 ≤ 푘 ≤ 2푛푐푛푐 − 1 ≤ log2 푘 ≤ 푛푐log2 푘 ∈ [푛푐 − 1, 푛푐]. (6.11)However, the upper-bound for the range generated by 푛푐 is always a power of 2 sothat 푘 can be such that log2 푘 = 푛푐 . Thus푛푐 = ⌈log2 푘⌉. (6.12)Similarly, from Equation 6.8 we get log2 푘′ ∈ [푛푒 − 1, 푛푒], though this time 푘′ canbe such that log2 푘 = 푛푒 − 1 so that푛푒 = ⌊log2 푘 + 1⌋. (6.13)Values generated by multiple 푛푐푖 and 푛푒푗 are used to name conformation spacesamples.Definition 6.3 (SampleName andResolution). Let푆푘 be a sample inℝ3×[0, 360◦)3.The name of 푆푘 is the vector푆푘 ∶= ⟨푘0, 푘1, 푘2, 푘3, 푘4, 푘5⟩ , (6.14)846.2. Formal Definitionswith 푘푖 ≥ 0 ∀ 푖. The resolution of 푆푘 is the vector returned by Res(⋅)Res(푆푘) ∶=⟨푛푐0 , 푛푐1 , 푛푐2 , 푛푒0 , 푛푒1 , 푛푒2⟩(6.15)where푛푐0 = ⌈log2 푘0⌉, 푛푒0 = ⌊log2 푘3 + 1⌋ (6.16)푛푐1 = ⌈log2 푘1⌉, 푛푒1 = ⌊log2 푘4 + 1⌋푛푐2 = ⌈log2 푘2⌉, 푛푒2 = ⌊log2 푘5 + 1⌋.The terms ‘sample’ and ‘name’ are synonymous.Table 6.4: The ranges of 푘 generated by 푛푐/푛푒.푛푐/푛푒 푛푐 Range 푛푒 Range0 [0,1] [0]1 [2] [1]2 [3,4] [2,3]3 [5,8] [4,7]4 [9,16] [8,15]5 [17,32] [16,31]6 [33,64] [32,63]7 [65,128] [64,127]8 [129,256] [128,255]9 [257,512] [256,511]10 [513,1024] [512,1023]11 [1025,2048] [1024,2047]12 [2049,4096] [2048,4098]13 [4097,8192] [4096,8191]14 [8193,16384] [8192,16383]The notation ‘푆푘’ references a name, not the subscript 푘. It’s possible to derivea unique value for 푘 from a name (Appendix A), however it isn’t as useful to workwith. As such, subscripts will be used solely to differentiate samples, such as 푆3and 푆9.Definition 6.4 (Normal Coordinates). The normal coordinates of 푆푘 is the vectorreturned by Norm(⋅)Norm(푆푘) ∶= ⟨푤0, 푤1, 푤2, 푤3, 푤4, 푤5⟩ (6.17)856.2. Formal Definitionswhere 푤0, 푤1, 푤2 ∈ [−1.1] and 푤3, 푤4, 푤5 ∈ [0◦, 360◦). Norm(푆푘) are the coor-dinates of 푆푘 in [−1, 1]3 × [0, 360◦)3.Construction of 푤푖 is described in Appendix B.Definition 6.5 (Absolute Coordinates). Let 푑 be the maximum linear distance be-tween base frame 퐹0 and frame 퐹6 for a given parametrization of a 6푅 chain35. Theabsolute coordinates of 푆푘 is the vector returned by Abs(⋅)Abs(푆푘) ∶= ⟨푎0, 푎1, 푎2, 푎3, 푎4, 푎5⟩ (6.18)= ⟨푑 ⋅푤0, 푑 ⋅푤1, 푑 ⋅푤2, 푤3, 푤4, 푤5⟩ (6.19)Abs(푆푘) are the coordinates of푆푘 in the original chainworkspaceℝ3×[0◦, 360◦)3.Definition 6.6 (Sample Adjacency). Let 푟 = ⟨푛0, 푛1, 푛2, 푛3, 푛4, 푛5⟩ be a sampleresolution and let 푆푢 and 푆푣 be two samples such thatRes(푆푢)[푖] ≤ 푟[푖] (6.20)Res(푆푣)[푖] ≤ 푟[푖], (6.21)with 0 ≤ 푖 ≤ 5. In other words, 푆푝 and 푆푞 exist at resolution 푟. Then, 푆푝 and 푆푞are adjacent at resolution 푟 if there exist no 푆푤, 푆푤 ≠ 푆푝 or 푆푞, that satisfies thefollowing two conditions1. Res(푆푤)[푖] ≤ 푟[푖] (6.22)and either of2푎. Norm(푆푝)[푖] ≤ Norm(푆푤)[푖] ≤ Norm(푆푞)[푖] (6.23)2푏. Norm(푆푞)[푖] ≤ Norm(푆푤)[푖] ≤ Norm(푆푝)[푖] (6.24)for all 푖 ∈ 0,… , 5.The conditions of Definition 6.6 define vertex adjacency on a lattice graph withvarying scales across axes. Consider, for example, the planar graph in Figure 6.4.The nodes (0, 0), (12 , 0), and (0, 1) are all adjacent, but 푆푝 = (0, 0) and 푆푞 = ( 12 , 1)are not because 푆푤 = (12 , 1) satisfies Condition 2a.For a full example, consider the two samples 푆1 and 푆2푆1 =⟨1, 5, 4, 7, 3, 9⟩ (6.25)푆2 =⟨6, 10, 1, 11, 2, 8⟩ (6.26)35In our case, 푑 is the maximum linear distance that atom 푃5 can be from 푃3 for a given set ofbond length and angle values.866.2. Formal DefinitionsFigure 6.4: A planar lattice graph whose x-axis components are half the scale ofthe y-axis components.which have normal coordinatesNorm(푆1) =⟨− 1, 34,−12, 315◦, 270◦, 67.5◦⟩ (6.27)Norm(푆2) =⟨14, 58,−1, 157.5◦, 90◦, 22.5◦⟩ (6.28)and resolutionsRes(푆1) =⟨0, 3, 2, 3, 2, 4⟩ (6.29)Res(푆2) =⟨3, 4, 0, 4, 2, 4⟩. (6.30)In addition, let the sample resolution be 푟 = ⟨3, 4, 2, 4, 3, 4⟩. At 푟, 푆1 and 푆2 areadjacent. Figure 6.5 illustrates why.Adjacency is defined at specific resolutions. If 푟[1] and 푟[2] were both anylarger, then 푆1 and 푆2 would no long be adjacent.That brings us to solutions, which also require unambiguous names.Definition 6.7 (Sample Solutions). Every sample 푆푘 consists of a set of solutions푠푘푖 of the form푠푘푖 ∶=⟨휃0, 휃1, 휃2, 휃3, 휃4, 휃5⟩ (6.31)with 휃푗 ∈ [0◦, 360◦) ∀푗 = 0,… , 5 being a torsion angle. Each 푠푘푖 is a unique IKsolution to a kinematic chain sampled at coordinates Abs(푆푘).Unlike samples, solutions don’t require explicit, vectorized names.There is no inherent ordering to solutions. However, numbering must be con-sistent. While any ordering will do, one system will prove particularly useful whenit comes time to optimize. The ordering is based on the absolute value of solutiontorsion angles.876.2. Formal DefinitionsFigure 6.5: A vertical diagram for determining sample adjacency. The left handside describes the (Res)olution, Name, and (Norm)al labels for the cartesian com-ponents of a sample, while the right hand side describes the eulerian, replacingnormal distances with angular ones. The central component shows the values gen-erated by 푟 = ⟨3, 4, 2, 4, 3, 4⟩ (green triangles), 푆1 and 푆2 (blue and red circles,respectively), and valid locations for any sample at resolution 푟 (white and greentriangles). To be adjacent, there must be at least one 푘푖 where there are no validlocations between 푆1 and 푆2 (i.e. no triangles between red and blue circles). Both푘1 and 푘2 satisfy this condition. Thus 푆1 and 푆2 are adjacent.886.2. Formal DefinitionsDefinition 6.8 (Absolute Torsion Angle). The absolute value of a torsion angle 휃푖is |휃푖| ∶={휃푖, if 휃푖 ≤ 180o360o − 휃푖, otherwise. (6.32)Solutions are ordered by increasing values of |휃0|, then |휃1|, etc. In the eventof ties, the smallest non-absolute value is used. For example, let 푠10, 푠11, and 푠12 bethe three solutions of some 푆1푠10 =⟨33◦, 167◦, 347◦, 12◦, 298◦, 101◦⟩ (6.33)푠11 =⟨92◦, 2◦, 311◦, 321◦, 134◦, 296◦⟩ (6.34)푠12 =⟨33◦, 193◦, 55◦, 277◦, 176◦, 4◦⟩. (6.35)As |푠11[0]| > |푠10[0]| = |푠12[0]|푠11 is last in the ordering. Since |푠10[0]| = |푠12[0]|, we need to look at the next indexto determine ordering for 푠10 and 푠12. While|푠10[1]| = |푠12[1]|,the non-absolute angles yield푠10[1] < 푠12[1].This implies that the ordering should be푠10 < 푠12 < 푠11.Definition 6.9 (Absolute Torsion Angle Ordering). Let 푆푘 be a sample with solu-tions 푠푘푖 . Then, the absolute (torsion angle) ordering of 푆푘 is the ordering of all 푠푘푖by the smallest absolute value |푠푘푖 [푗]|, for increasing indices 푗 beginning at 푗 = 0.Ties are broken by the smallest non-absolute value, 푠푘푖 [푗].For the remainder of this work, an absolute ordering of solutions will be as-sumed in all cases.It should be noted that absolute coordinates are defined as a scaling of normalcoordinates, not the other way around. This is done to emphasis the independence ofour modelling technique from any specific 6푅 chain parametrization. Parametriza-tions are treated as special cases of a generalized normal form.The notion of distance between two arbitrary solutions 푠푝푢 and 푠푞푣 is an importantone.896.2. Formal DefinitionsDefinition 6.10 (Angular Distance Between Solutions). The angular distance be-tween two angles 휃, 휙 ∈ [0◦, 360◦) isd(휃, 휙) ∶= |휃 − 휙|. (6.36)The angular distance between two vectors of angles of equal length 휃 = ⟨휃0, 휃1,… , 휃푚⟩and 휙 = ⟨휙0, 휙1,… , 휙푚⟩ isd(휃, 휙) ∶=푚∑푖=0d(휃푖, 휙푖). (6.37)The angular distance between two solutions 푠푝푢 and 푠푞푣 can therefore be written asd(푠푢푝, 푠푣푞). (6.38)Angular distances arise from modelling changes in solution torsion angles re-sulting from small changes in the location of 푄 in its workspace. These smallchange in 푄 correspond to moving between adjacent samples on the normalizedsampling lattice. We can thus drop all reference to 푄 and deal strictly with (thenormal coordinates of) sample points. We’ll demonstrate how with an exampleusing the 3푅 planar chain of Figure 5.5(a).Consider the two solutions of 푆0 in Figure 6.6,푠00 =⟨135◦, 90◦, 225◦⟩ (6.39)푠01 =⟨45◦, 270◦, 135◦⟩. (6.40)At sufficiently high resolutions, an adjacent solution푆1 will have the same num-ber of solutions as it will be in the same region36, whose torsion angles are similarto those of 푆0, say푠10 =⟨120◦, 120◦, 210◦⟩ (6.41)푠11 =⟨60◦, 240◦, 150◦⟩. (6.42)The angular distances between the first solutions and the second solutions of 푆0 and푆1d(푠00, 푠10) = 60◦d(푠01, 푠11) = 60◦36See Theorem 7.2.906.2. Formal DefinitionsFigure 6.6: An example of conformational paths for a planar 푅3 chain. At eachsample point (red circle) 푆푖, there are two distinct solutions, 푠푖0 and 푠푖1. If successive푆푖 are assumed to be adjacent at some resolution, then the sequences 푠00 − 푠10 − 푠20and 푠01 − 푠11 − 푠21 represent two disjoint conformational pathways from 푆1 to 푆3.With the incorporation of 푆4, however, the paths are no longer disjoint: 푠00 − 푠10 −푠20 − 푠30 − 푠21 − 푠11 − 푠01 is a conformational path.are much less than between 푠00 and 푠11, and 푠01 and 푠10d(푠00, 푠11) = 300◦d(푠01, 푠10) = 300◦.Assume a new sample 푆2 adjacent to 푆1 (Figure 6.6) with solutions푠20 =⟨105◦, 150◦, 195◦⟩ (6.43)푠21 =⟨75◦, 210◦, 165◦⟩. (6.44)Then similar results exist between the solutions of 푆1 and 푆2d(푠10, 푠20) = 60◦d(푠11, 푠21) = 60◦d(푠10, 푠21) = 180◦d(푠11, 푠20) = 180◦.916.2. Formal DefinitionsThere is a kind of natural ‘path’ between 푠00, 푠10, and 푠20, as well as between 푠01, 푠11,and 푠21. These are the conformational pathways of the sample sequence푆0−푆1−푆2.If we were to continuously ‘pull’ the end-effector from its position at 푆0 to 푆2 inFigure 6.6, it’s clear that 푠00 would transform into 푠10, then into 푠20. Similarly with푠01, 푠11, and 푠21. The pathways are discreet approximations of an otherwise smoothtransformation.A problem occurs when the number of solutions at a sample changes. In Figure6.6, 푆3 only has one solution푠30 =⟨90◦, 180◦, 180◦⟩. (6.45)Both the solutions at 푆2 are equidistant from 푠30d(푠20, 푠30) = 60d(푠21, 푠31) = 60,violating what was previous bijection between solutions in adjacent samples. This‘collapsing’ of solutions (or ‘expansion’, if going from fewer to more) is termed asingularity 37.Definition 6.11 (Singularity). A singularity is a pair of adjacent samples 푆푢 and푆푣 such that |푆푢| ≠ |푆푣|. An edge in a sampling lattice is a singular edge if it isadjacent on a singularity.It should be clear that the angular distance between any two solutions of thesame sample, 푠푘푖 and 푠푘푗 , is always non-zero. If d(푠푘푖 ,푠푘푗 ) were zero, they would ceaseto have distinct torsion angles, implying that 푠푘푖 = 푠푘푗 . This yields an interestingproperty: no conformational pathway exists between 푠푘푖 and 푠푘푗 in the absence ofsingularities. In order to for a conformational pathway to exist between 푠푘푖 and 푠푘푗 ,passage through a singularity must occur. This is apparent for 푠00 and 푠01 in Figure6.6 and is proved for general kinematic chain conformation spaces in Theorem 7.2.Definition 6.12 (Conformational Pathways). Let 푆 be a path on a sampling lattice푆 ∶= 푆0 − 푆1 −⋯ − 푆푛 (6.46)37Singularities also occur in the proper study of kinematic chains, representing losses of linearindependence between certain axes in lower pairs, often producing sample points with infinite IKsolutions. Our usage of the term is strictly to indicate changes in the number of solutions, or regionalboundaries. We won’t be working with ‘proper’ singularities, so there should be no difficulty in usingthe terminology.926.2. Formal Definitionsand let 푚 = max{|푆0|, |푆1|,… , |푆푛|}. In addition, let 푃 be an ordered set of 푚vectors 푝푖 of samples solutions푝푖 ∶=⟨푠0푎0 , 푠1푎1,… , 푠푛푎푛⟩(6.47)on 푆, denoted by 푃 (푆). Then each 푝푖 is a conformational pathway, or conpaths,and 푃 (푆) is a bundle of conpaths. Let the weight of any conpath 푝푘 bew(푝푘) =푛−1∑푖=0푑(푠푖푎푖 , 푠푖+1푎푖+1). (6.48)푃 (푆) is a bundle of potential conpaths if every solution 푠푝푢 of every sample 푆푝 is anelement of at least one conpath 푝푘38.The weight of a bundle 푃 (푆) isw(푃 (푆)) ∶= ∑푝푘∈푃w(푝푘). (6.49)푃 (푆) is a bundle of likely conpaths if 푃 (푆) has the smallest weight of all possiblebundle of potential conpaths on 푆.The difference between potential and likely conpaths is one of weighting. Inthe next chapter, we’ll see that bundles of conpaths with smaller weightings will,at sufficiently high sampling resolutions, better reflect path connectedness in theactual conformation space being approximated.Conformational pathways, can be extended into include entire sampling lattices.Definition 6.13 (Conformational Pathways of a Sampling Lattice). Let  be a sam-pling lattice and  be a set of bundles of potential conpaths on  consisting ofexactly one bundle 푃푝푞 on every pair of adjacent samples 푆푝 and 푆푞 in .  iscalled a conpath bundle set.Two solutions 푠푝푢 and 푠푞푣 are considered path connected in () if there exists asequence of solutions푠푝푢 − 푠푎1푏1− 푠푎2푏2 −⋯ − 푠푎푚푏푛− 푠푞푣 (6.50)where every successive pair of solutions 푠푟푖 and 푠푡푗 form a conpath in bundle 푃푟푡.Let 푝푝푞푢푣 be a path between 푠푝푢 and 푠푞푣 for a given (). Then () is a feasible ifthe following conditions hold:푝 = 푞 ⟹ ∃ 푠푟푖 , 푠푡푗 ∈ 푝푝푞푢푣 ∋ |푆푟| ≠ |푆푡|. (6.51)38i.e. the conpaths of 푃 (푆) cover the solution samples of 푆936.2. Formal DefinitionsIn other words, there only exists a path between two solutions in a single sample ifthe path passes through a singularity. If () is not feasible, it’s infeasible.Let ℙ() be the set of all feasible bundle sets 푘 for sampling lattice  and letthe weight of any 푘 bew(푘) ∶= ∑푃 푘푝푞∈푘w(푃 푘푝푞). (6.52)The bundle set in ℙ which has minimal weight is the optimal conformational spacefor .The relationship between sampling lattices and conformational pathways withstacked graphs and assignments should be apparent. Every sampling lattice can berepresented by a stacked graph 픾, every bundle set  on  corresponds to a uniqueassignment 퐴 on 픾, and feasibility of () is the same as feasibility on 퐴(픾). Asthe size of edge stacks and the disjoint paths of their assignments define regionsand layers in 픾 and 퐴(픾), respectively, so too do bundle sizes and conpaths defineconformational regions and conformational layers in  and (), respectively.Definition 6.14 (Conformational Regions and Layers). Let  be a sampling latticefor a workspace and  be a feasible bundle on . In addition, let ′ be  less allsingular edges. Then  ∶= {푅푖|푖 = 0, 1, 2,…} (6.53)is the set of path connected components, or conformational regions, 푅푖 of ′ while푖 ∶= {퐿푖푗|푗 = 0, 1, 2,…} (6.54)is the set of path connected components, or conformational layers, 퐿푖푗 of (푖).94Chapter 7Stacked Graphs of ConformationSpacesIn this chapter, we formally re-write sampling lattices in the language of stackedgraphs. Prior to doing this, we must demonstrate that sampling lattices actuallyapproximate conformation spaces as well as prove the path-disjointedness of anytwo sample solutions 푠푘푖 and 푠푘푗 in the absence of singularities. The process of doingso is reminiscent of Section 2.1, where we introduced the process of approximatingan unknown function 푓 using ‘special pairs’ of approaching images (i.e. samplesolutions). In what follows below, approaches are defined in terms of shrinkingopen neighbourhoods and limits.Kinematic chains are manifolds [McC90]. As sampling resolution increases,the distance between solutions for adjacent samples points on the sampling latticedecrease, with the distance between certain pairs of approaching 0◦ in the limit.These pairs are what defined conformational pathways in the previous chapter. Wenow prove that conpaths, as described in Definition 6.13, exist in connected mani-folds. The proof assumes some knowledge of topology.Definition 7.1 (Manifold). [Mun00] An m-manifold is a Hausdorff space 푌 with acountable basis such that each point 푦 of 푌 has a neighbourhood that is homeomor-phic with an open subset of ℝ푚.Theorem 7.2 (Layers and Regions of Manifolds). Let 푓 be a continuous functionon a connected metric space 푋푓 ∶ 푋 → 푌 (7.1)such that 푌 is an 푚-manifold and 푓−1 is multi-valued on at least some 푦푖 ∈ 푌 .Denote the set of pre-images 푓−1(푦푖) as 푆푖푆푖 ∶= {푥푖푗|푥푗 ∈ 푓−1(푦푖)}. (7.2)In addition, let퐾 be a connected set in 푌 where |푆푖| = |푆푗| for all 푘푖, 푘푗 ∈ 퐾 , with푋퐾 ∶= 푓−1(퐾) =⋃푘푖∈퐾푆푖. (7.3)95Chapter 7. Stacked Graphs of Conformation SpacesThen for each 푘푖 ∈ 퐾 , all 푥푖푗 ∈ 푆푖 are mutually path disconnected in 푋퐾 . Thesecomponents are the sub-layers h퐾푖 of 푋퐾 .The boundary of 푌 under 푓 is the set of boundary points 퐵 in 푌 , where 푏 ∈ 푌is a boundary point if every neighbourhood of 푏 contains at least two points 푦푟 and푦푡 such that |푆푟| ≠ |푆푡|. A layer 푖 of 푋 under 푓 is a connected component in푓−1(푌 − 퐵), with the set of all layers denoted as ℍ푋 .The regions of 푌 under 푓 are the connected components of 푌 − 퐵.Proof. The proof for the path disconnectedness of all 푥푖푗 ∈ 푋푘 for all 푗, for a given푖, is by contradiction.For any 푥푝푎, 푥푝푏 ∈ 푆푝, 푦푝 not a boundary point, the distance between 푥푝푎 and 푥푝푏is푑(푥푝푎, 푥푝푏) > 0 (7.4)when 푎 ≠ 푏. This follows immediately from the fact that 푥푝푎 and 푥푝푏 are distinctvalues in 푋. Next, let 퐵푝 be an open 푚-ball centred on 푦푝 with radius 푒 and whichdoesn’t include a boundary point. Since 푌 is Hausdorff, such a neighbourhoodalways exists. For any 푦푞 ∈ 퐵푝, the following two conditions hold:1. for each 푥푝푢 ∈ 푆푝 there is exactly one 푥푞푣 ∈ 푆푞 such that푑(푥푝푢, 푥푞푣)→ 0 as 푒→ 0, (7.5)2. for each 푥푞푣 ∈ 푆푞, there is exactly one 푥푝푢 ∈ 푆푝 such that푑(푥푝푢, 푥푞푣)→ 0 as 푒→ 0. (7.6)Assume that these are not true. Then there are four cases, two for each condi-tion. We treat the first condition only as the proofs for the second are similar.In the first case, there exists an 푥푝푢 such that there is no 푥푞푣 where푑(푥푝푢, 푥푞푣)→ 0 as 푒→ 0. (7.7)In the limit of 푒 → 0, 퐵푝 → 푦푝39. Thus, 푦푞 → 푦푝 as 푒 → 0. However, this impliesthat 푥푞푣 ∈ 푆푝 in the limit, meaning that|푆푝|→ |푆푝| + 1 as 푒→ 0. (7.8)This is impossible. Therefore there must be at least one 푥푞푣 ∈ 푆푝 for every 푥푝푢 ∈ 푆푞such that푑(푥푝푢, 푥푞푣)→ 0 as 푒→ 0. (7.9)39i.e. the open ball contracts to point 푦푝 at its centre96Chapter 7. Stacked Graphs of Conformation SpacesIn the second case, there exist at least two elements in 푆푞 such as Equation 7.5holds. Let these be 푥푞푎 and 푥푞푏. However, the existence of 푥푝푎 and 푥푝푏 imply that 퐵푝contains a branch point, which, by definition, it doesn’t. Specifically, in the limit of푒→ 0, |푆푞|→ 푘 with 푘 < |푆푞|: the size of 푆푞 shrinks as 푆푞 → 푆푝.This is a contradiction. Therefore there exists at most one 푥푞푣 ∈ 푆푞 such thatEquation 7.5 holds.Therefore, for any 푆푘, every 푥푘푖 ∈ 푆푘 is path disconnect in 푆. In addition, thisimplies that if 푥푘푖 and 푥푘푗 are path connected in 푓−1(푌 ), the path must contain aboundary point.Corollary 7.3. Let 푋, 푌 , 푓 , and 퐵 be as in Theorem 7.2. Then, for any 푥푝푢, 푥푞푣 ∈푓−1(푌 −퐵), 푥푝푢 and 푥푞푣 in different layers, every path connecting 푥푝푢 and 푥푞푣 containsat least one boundary point 푏.Proof. Since 푥푝푢 and 푥푞푣 belong to difference layers, they are path disconnected in푓−1(푌 −퐵). Therefore, if their path connected in 푓−1(푌 ), it must be through someelement in 퐵.Given that Equation 5.2 is continuous on a connected metric space, Theorem7.2 applies to kinematic chains with the boundary points equivalent to singularities(Definition 6.11). The key difference is that in sampling lattices we treat infiniteIK solutions as boundaries as well, the reason for which being that stacked graphshave not been generalized to infinite stack sizes.Boundary points may be similar to branch points in complex functions. As Ihave not studied complex analysis - and to avoid digression into yet another math-ematical field - the notion of boundary points are used instead.It should be clear from Corollary 7.3 and the proof of Theorem 7.2 why it’s theminimally weighted potential conpath bundles are what we’re interested in: so longas our sampling lattice  gives good coverage of the workspace, and so long as asufficiently high number of samples are used, the connected components in ()approximate the layers of 푄−1.Re-writing a sampling lattice as a stacked graph is straightforward.Definition 7.4 (Stacked Graphs of Sampling Lattices). Let  be a sampling latticeconsisting of samples 푆푖, each composed of a set of solutions 푠푖푗 . Then the stackedgraph formed on  is 픾 = ( , ), where 푉푖 ∈  if 푆푖 ∈ , 퐸푝푞 ∈  if 푆푝 and 푆푞are adjacent in , and 푒푝푞푢푣 ∈ 퐸푢푣 if 푠푝푢 ∈ 푆푝 and 푠푞푣 ∈ 푆푞.The weight of any 푒푝푞푢푣 is푤푝푞푢푣 ∶= 푑(푠푝푢, 푠푞푣). (7.10)An edge stack퐸푝푞 is singular if and only if |푆푝| ≠ |푆푞| and asingular otherwise.977.1. Validating the ULA Constraint and Disconnecting Assignment ComponentsTheorem 7.5. Let  be a sampling lattice graph and픾 be the stacked graph formedon it. Then, for any path 푆 in , every bundle 푃 on 푆 is isomorphic to a uniqueassignment 퐴 on  in 픾, where  is the path stack associated with 푆. Thus, ()is feasible or optimal if and only if 퐴(픾) is feasible or optimal, respectively.Proof. That every bundle is isomorphic to an assignment is obvious. The rest fol-lows directly from the isomorphism.The structure of 픾, the vertex stacks and their adjacency, is defined by the tech-nique used to sample space푋, with assignments 퐴 on 픾 representing possible pre-images and connected components of 푌 and 푌 −퐵 under 푓 . The weightings of eachedge in 픾, the distances between point-wise pre-images 푓−1(푦푖), are what guidethe choice in which assignment best represents 푓−1(푌 ) or 푓−1(푌 − 퐵).It should be emphasised that Theorem 7.2 and Corollary 7.3 apply to any con-tinuous functions on a connectedmetric space that producemanifolds, not just thosedealing with kinematic chains. Stacked graphs can therefore be used as a tool forstudy certain classes of manifolds.7.1 Validating the ULA Constraint and DisconnectingAssignment ComponentsIn Section 2.5 we introduced the non-basic Uniform Layer Adjacency (ULA)constraint for singular edge stacks. The rational given for it was so that the pro-portional and binary forms of the derived assignment 퐴(ℝ픾) would be the same(Lemma 2.43), which would assist in calculating metrics for how well optimal as-signments approximate conformation manifolds (Chapter 8). Enforcing ULA usinglinear programming is, however, not straightforward (Section 4.3), and increasingthe difficulty of one set of calculations to easy another set does not imply an over-all reduction in complexity. There should be a inherent reason for using ULA. Weprovide such a rational in this section by demonstrating the conformation spacesexhibit the ULA property, or some variation of it.Returning to the annulus boundary example of Section 2.1, with the primaryimage reproduced in Figure 7.1 below, we’ll recall that singularities were introducedas size discrepancies between successive image sets 푓 (푥푖) and 푓 (푥푖+1). In terms ofstacked graphs, this correspond to asingular edge stacks. One such singularity isbetween the images of 푥3 and 푥4. What is visually quite clear is that singularities tonot uniformly impact the images they include. The existence of an edge between 푦31and 푦42 and another between 푦30 and 푦41 (Figure 7.1(b)) is questionable, however theedge between 푦31 and 푦43, and that between 푦30 and 푦40, are certainly not. Regardless of987.1. Validating the ULA Constraint and Disconnecting Assignment Componentshow points on the outer ring related to those of the inner ring, intra-ring adjacencyis fixed.In terms stacked graphs, for any asingular퐸푝푞, |푉푝| > |푉푞| if their exist a pair 푣푝푖and 푣푞푗 such that the distance between them approaches zero in the sampling limit,then a singularity should have no impact on adjacency of the layers which 푣푝푖 and푣푞푗 belong to. There is some degree of independence suggesting a degree of uni-form adjacency between certain layers of adjacent regions. Whether this propertyis exactly ULA is an open question, but one which merits the use of ULA until theproper constraint(s) can be derived.On the other hand, the existence of pairs 푣푝푖 and 푣푞푗 which do not approach eachother in the limit gives a mechanism for identifying disjoint components in 푓 (푋).Clearly, 푦31 and 푦42 do not approach each other, nor do 푦30 and 푦41. If the set 푆 isenlarged to include samples between 푥3 and 푥4, and it’s found that the same lack ofconvergence occurs, then this would be strong evidence for the existence of disjointcomponents or layers in 푓 (푋). If an optimal assignment 퐴 on 픾 is found and a lackof convergence is discovered, any edge 푒푝푞푖푗 in 퐴(픾) whose flow value 푥푝푞푖푗 is 1, butwhose weight푤푝푞푖푗 - which corresponds to angular distance - is not sufficiently closeto zero can be be deleted from 퐴(픾). Deleting all offending edge stacks could pro-vide a more accurate approximation. Figure 7.2 does this for our annulus example.997.1. Validating the ULA Constraint and Disconnecting Assignment Components(a)(b)Figure 7.1: (a) The annulus 푓 (푋) of Section 2.1 and (b) and optimal linear approx-imation to it based on the sampling regime.1007.1. Validating the ULA Constraint and Disconnecting Assignment ComponentsFigure 7.2: More accurate approximations of 푓 (푋) can be had removing the edgesbetween successive image elements 푦푖푎 and 푦푖+1푏 whose mutual distance are sus-pected to be non-diminishing in the sampling limit.101Chapter 8Conformation Space SimulationsIn Chapters 2 and 3 we explored the mathematics of stacked graphs and, inChapters 5 through 7, approximated the conformation spaces of kinematic chainsand nucleic acid phosphate backbones using these structure. The conformationspace problem for was reduced, in Chapter 7, to finding an optimal feasible assign-ment, a problem that was solved in Chapter 4 through the construction of a linearprogram that satisfied the assignment feasibility conditions of Theorem 2.31. Thischapter develops a collection metrics to study how well an optimal assignment ap-proximates a conformation space. In addition, it generalizes what has thus far beenthe study of rigid chains to semi-rigid chains, allowing us to account for flexibilityin chemical bond lengths and angles.For this chapter, all stacked graphs픾 are assumed to be associated with normal-ized lattices generated by sampling a chain conformation space using the bisectiontechnique described in Chapter 6 at some fixed resolution (Definition 7.4). Unlessotherwise stated, all assignments 퐴 are assumed to be optimal. Graphs of the form퐴(픾) will henceforth be termed conformation graphs. When referring to normalcoordinates and vertex stacks, Norm(푉푘)will be used as a short hand for ‘Norm(푆푘),where 푆푘 is the sample associated with 푉푘’ (see Definition 7.4).Definition 8.1 (Similar and Dissimilar Stacked Graphs). Let픾 and픾′ be generatedby two different chain parametrizations. If the parametrizations are approximatelythe same, then 픾 and 픾′ are similar, otherwise they are dissimilar.Whether two parametrizations are ‘approximately the same’ is context depen-dant. For our purposes, parametrizations drawn from the same distributions willusually be similar.8.1 Comparing Normalized WorkspacesThis section discusses four possible congruence metrics for comparing stackedgraphs: Ω퐴∗ , Ω푉 , Ω, and Ω . Additional metrics are certainly possible.1028.1. Comparing Normalized Workspaces8.1.1 퐴∗ Congruence Metric Ω퐴∗In Chapter 2 we introduced the identity assignment 퐴∗ (Definition 2.38). Itturns out that, besides being the graph dual of the identity element in 핊푚 (Fact 3.3),퐴∗ is potentially an optimal feasible assignment for asingular edge stacks at infinitesampling resolutions. This applies only in the case where an absolute torsion angle(Definition 6.9) or equivalent ordering is used. The result stems from the continuousnature of conformation spaces.Recall from Theorem 7.2 and its proof that for pairs of adjacent samples 푆푝 and푆푞 in the same region, there exists, for each sample 푠푝푢, precisely one sample 푠푞푣 suchthat the angular distance between 푠푝푢 and 푠푞푣 approaches 0◦ as the distance between푆푝 and 푆푞 approaches zero40. In the context of stacked graphs, this means that theweight for edge 푒푝푞푢푣 is nearly zero at sufficiently high resolutions, with 푢 = 푣 underabsolute ordering. The absolute torsion angle ordering ensures that, at sufficientlyhigh resolutions, two vertices having the same second index, belonging to adjacentvertex stacks, and existing in the same region, have nearly identical correspondingangular solution vectors (Definition 6.7).The implication is that at high resolutions퐴∗ is a nearly optimal (i.e. minimallyweighted feasible) assignment for asingular 퐸푝푞, and by extension, for every region푖 ∈ 픾. The graph dual interpretation is that 훼푝푞 ≈ 휄 for all 푝, 푞.With this in mind, it’s possible to define a single value that reflects how well aparticular sampling regime approximates the finite IK components of a conforma-tion space.Definition 8.2 (퐴∗ Convergence Metric Ω퐴∗). Let 퐴 be any feasible, though notnecessarily optimal, assignment on some 픾. Then the 퐴∗ convergence metric for퐴(픾) isΩ퐴∗(퐴(픾)) ∶=∑퐴푝푞∈퐴(픾̐)|푉푝|∑푖=0푥푝푞푖푖∑퐸푝푞∈픾̐|푉푞| . (8.1)Equivalently,Ω퐴∗ is the ratio between the number of identity transpositions (푖푖)in the graph dual 훾 of 픾 and the total number of possible identity transpositions41.Lemma 8.3. If 푥푖푗 ∈ {0, 1}, Ω퐴∗(퐴(픾)) → 1 as the sampling resolution of 픾approaches infinity.40i.e. as the radius of 퐵푝 goes to zero.41Under the assumption that the transposition representation is minimal (Section 3.1).1038.1. Comparing Normalized WorkspacesOne issue with usingΩ퐴∗ is that the value can be misleading at low resolutions.It’s entirely possible that Ω퐴∗(퐴(픾)) = 1, with Ω퐴∗ decreasing dramatically beforeconverging once more to 1 at high resolutions.Another issue is that the convergence rate ofΩ퐴∗ is both unknown and likely de-pendent on the details of the conformation space being approximated. Convergenceis predicted to be non-uniform within a region as areas near singular boundaries areexpected to converge slower then areas distant from them. This prediction is basedon the kinematic singularities that haunt singular edge stacks, which can producesextremely high angular velocities [Ang07], manifesting as large angular distancesbetween the solutions of adjacent samples even when resolutions are high. It may,however, be possible to approximate convergence rates by locally sampling confor-mation spaces at high resolutions and averaging the resulting convergence values.This approach is not covered here.8.1.2 Vertex Stack Congruence Metric Ω푉When comparing two similar stacked graphs 픾 and 픾′, it’s not necessary thatboth exist at the same resolution. One can compare vertex stacks which exist inboth 픾 and 픾′, corresponding to vertex stacks having the same normal coordinates(Definition 6.4).Definition 8.4 (Shared Vertex Stacks ∩푉 ). For any two 픾 and 픾′, the shared vertexstacks of 픾 and 픾′ are픾 ∩푉 픾′ ∶= {푉푖|푉푖 ∈ 픾, 푉 ′푗 ∈ 픾′,Norm(푉푖) = Norm(푉 ′푗 )}. (8.2)Definition 8.5 (Vertex Stack Congruence MetricΩ푉 ). Let픾 and픾′ be two stackedgraphs and ̃ ∶= 픾 ∩푉 픾′. (8.3)Then the vertex stack congruence metric of 픾 with respect to 픾′ isΩ푉 (픾,픾′) ∶= 1 −∑푉̃푖∈̃||푉푖| − |푉 ′푖 ||∑푉̃푖∈̃|푉푖| . (8.4)For graph duals, the metric is a comparison between the size of the symmetricgroups that a vertex dual belongs to in 훾 and 훾 ′.Though simplistic, Ω푉 is straightforward to calculate, providing a quick anddirty comparison technique that doesn’t require expensive assignment calculations.Intuitively, if 픾 and 픾′ are similar and Ω푉 (픾,픾′) ≈ 1, then the conformationalspaces should be nearly identical.1048.1. Comparing Normalized WorkspacesLemma 8.6. For any two 픾 and 픾′ generated by the same chain parametrizations,but possibly at different sampling resolutions, Ω푉 (픾,픾′) = Regional Congruence Metric ΩHigher level comparisons between similar stacked graphs begin with identify-ing regions between them.Definition 8.7 (Regional CongruenceMetricΩ). Let픾푎 and픾푏 be similar stackedgraphs at the same resolution. Let 픾푐 be a stacked graph consisting of two vertexstacks 푉푎 and 푉푏, where푉푎 ∶= {푣푎푖 |푖 ∈ 픾푎} (8.5)and푉푏 ∶= {푣푏푗 |푗 ∈ 픾푏}, (8.6)and a single edge stack 퐸푎푏. Assign to each 푒푎푏푖푗 a positive weight 푤푎푏푖푗 . Then, when퐴(픾푐) is optimal.Ω(픾푎,픾푏) ∶= 1 − 퐴(픾푐) (8.7)is a regional congruence metric if the weights 푤푎푏푖푗 are defined such thatΩ(픾푎,픾푏)→ 1 (8.8)as the parametrizations of 픾푎 and 픾푏 approach each other.If 푎푖 ∈ 픾푎 and 푏푗 ∈ 픾푏 are adjacent in 퐴(픾푐)42, then 푎푖 and 푏푗 identifywith each other, denoted by푎푖 ≡ 푏푗 . Otherwise,푎푖 and푏푗 do not identify witheach other, or푎푖 ≢ 푏푗 .The optimal feasible assignment 퐴(픾푐) identifies, for each region in 픾푎, theregion in 픾푏 that best correlates with it, based on the weighting metric chosen. Ifthe parametrizations of픾푎 and픾푏 are sufficiently close, then퐸푎푏 is likely asingularand the total weight of 퐴(픾푐) should be nearly zero regardless of the weightingscheme used. One weighting scheme is based on centres of mass.Definition 8.8 (Centre of Mass). Let  be a set of vertex stacks 푉푖 associated withsome 픾. Assign to each 푉푖 a mass Mass(푉푖). Then Norm() are the normal coordi-nates for the centre mass of the vertex stacks using normal coordinates. The centreof mass for 픾 is Norm(픾).42That is, if 푥푎푏푖푗 = 1.1058.1. Comparing Normalized WorkspacesFigure 8.1: The regions of both픾푎 and픾푏 are treated as vertices in vertex stacks ofa new 픾푐 . Edges weights (suppressed) between ‘region vertices’ are a measure ofdifference between the two regions, such as distance between centres of mass. Theoptimal feasible assignment퐴 on픾푐 (red lines) identify the regions of픾푎 with thoseof 픾푏. Bold black edges indicate adjacency between regions in the same stackedgraph.Inmost cases, themass of each vertex stack will all be 1. Regions, being stackedgraphs, have centres of mass. The weights 푤푎푏푖푗 are simply the euclidean distancebetween Norm(푎푖 ) and Norm(푏푗 ).One problem withΩ is that it doesn’t necessarily preserve regional adjacency.In Figure 8.1,푎0 and푎2 are both adjacent in픾푎, and are identified with the푏0 and푏1, respectively, which are likewise adjacent in픾푏. This is to be expected as픾푎 and픾푏 are assumed to be similar. However, there is a problem with the identifications푎0 ≡ 푏0 and 푎1 ≡ 푏1 as 푎0 and 푎1 are adjacent but 푏0 and 푏1 are not. Theidentification in Figure 8.1 does not preserve regional adjacency.Adjacency can be preserved with the following restrictions.Definition 8.9 (Regional Adjacency Constraint). Let푎푖 and푎푗 be regions in 픾푎,푏푥 and푏푦 be regions in 픾푏, with 픾푎 and 픾푏 similar. Then푎푖 ≡ 푏푥 and 푎푗 ≡ 푏푦 (8.9)only if ̉푖푗 = ∅ and ̉푥푦 = ∅ (8.10)or ̉푖푗 ≠ ∅ and ̉푥푦 ≠ ∅. (8.11)1068.1. Comparing Normalized WorkspacesThe regional adjacency constraint is similar to the non-basic ULA constraint inSection 2.5.Note that Definition 8.9 says nothing about adjacency when two regions in 픾푎identify with the same region in 픾푏, and vice versa. The identifications of 푎1 and푎2 with푏1 in Figure 8.1 are therefore valid.Like Ω푉 , Ω can be performed in the absence of assignments.8.1.4 Layer Congruence Metric ΩWhen the regions of similar 픾푎 and 픾푏 have been identified and optimal as-signments have been calculated for both, the next natural comparison is betweenthe layers of both assignments. The process is identical to regional identification,save for being based on regional stacked graphs (Definition 2.35).Definition 8.10 (Layer Congruence Metric Ω). Let 픾푎 and 픾푏 be similar, haveidentified regions, and have optimal assignments 퐴푎 and 퐴푏, respectively. If theregional stacked graphs of 픾푎 and 픾푏 are ℝ픾푎 and ℝ픾푏 , respectively, denote theirvertex stacks as 푉 푎푖 and 푉 푏푗 , respectively.Create a new stacked graph 픾푐 composed of the vertex stacks of both ℝ픾푎 andℝ픾푏 , where 퐸푎푏푝푞 ∈ 픾푐 if푎푝 ≡ 푏푞.Assign to each 푒푎푏 푝푞푖푗 a positive weight 푤푎푏 푝푞푖푗 . ThenΩ(픾푎,픾푏) ∶= 1 − 퐴(픾푐), (8.12)where 퐴(픾푐) is optimal, is a layer congruence metric if the weights 푤푎푏 푝푞푖푗 are de-fined such thatΩ(픾푎,픾푏)→ 1 (8.13)as the parametrizations of 픾푎 and 픾푏 approach each other.Layer 푎 푝푖 in 퐴푎(픾푎) is adjacent to layer 푏 푞푗 if 푥푎푏 푝푞푖푗 = 1. If so, they identify,푎 푝푖 ≡ 푏 푞푗 . Otherwise, they do not identify, 푎 푝푖 ≢ 푏 푞푗 .Distances between centres of mass, this time for layers in 퐴푎(픾푎) and 퐴푏(픾푏),provide a weighting scheme that produces a layer congruence metric.As withΩ, when the regions of픾푎 and픾푏 consist of more than one layer each,issues of layer adjacency preservation in Ω can arise. For example, let 픾푎 and 픾푏consist of two regions each: 푎0,푎1,푏0, and 푏1, where |푎0| = 4, |푎1| = 3,|푏0| = 3 and |푏1| = 4. To simplify matters, assume that the derived assignments퐴푎(ℝ픾푎) and 퐴푏(ℝ픾푏) are binary (Definition 2.36), and that layer adjacency is thatdescribed by the assignment in Figure 8.2. We’ll also assume that regional identi-fication is 푎0 ≡ 푏0 and 푎1 ≡ 푏1. Finally, let 퐴푐(픾푐) be as illustrated in Figure8.2.1078.1. Comparing Normalized WorkspacesFigure 8.2: The assignments on 퐸푎01 and 퐸푏01 are the derived assignments 퐴푎(ℝ픾푎)and 퐴푏(ℝ픾푏), respectively, indicating layer adjacency. The red lines indicate theassignment 퐴푐(픾푐), which is also indicates layer identification.Layer identities 푎 01 ≡ 푏 02 and 푎 10 ≡ 푏 13 preserve layer adjacency since푥푎푎 0110 = 1 in 퐴푎(ℝ픾푎) (8.14)and푥푏푏 0123 = 1 in 퐴푏(ℝ픾푏) (8.15)On the other hand, we have 푎 02 ≡ 푏 01 and 푎 12 ≡ 푏 11 , which don’t preserveadjacency as푥푎푎 0122 = 1 in 퐴푎(ℝ픾푎) (8.16)but푥푏푏 0111 = 0 in 퐴푏ℝ픾푏 . (8.17)Visually, two red edges 푒푎푏 푥푦푖푗 and 푒푎푏 푤푧푘푙 preserve adjacency if both 푒푎푎 푥푤푖푘 and푒푏푏 푦푧푗푙 are black in Figure 8.2.As with regions in Ω, layer adjacency in Ω can be enforced with an addi-tional constraint. The constraint is exactly the Uniform Layer Adjacency constraintdiscussed in Section 2.5 (Definition 2.42).The assumption of binary 퐴(ℝ픾푎) and 퐴(ℝ픾푏) is a large one. In its absence,assignments are proportional, resulting in layer identifications that are also pro-portional. ‘Proportional adjacency’ is something we wish to avoid at this stage of1088.1. Comparing Normalized Workspacesresearch, which is one of the reasons we introduced binary derived assignmentsto begin with (Definition 2.36). We also have reason to suspect that conformationspace are binary in nature, as noted in Section 7.1.It’s possible to calculate Ω in the absence of Ω, in which case the layers of픾푎 and 픾푏 each form a single vertex stack. If 픾푎 and 픾푏 are sufficiently similar,then the loss of regional data should not impact optimal identifications.We noted at the end of Section 2.3 that regional stacked graphs give a broad-scale description of the conformational pathways between conformations. Full con-formation graphs are large, complex structures whose size is exponential to theirsampling resolution (Equation 6.4), but regional stacked graph sizes eventually sta-bilize since the number of regions and layers for conformation graphs are finite43. Ifthe resolution is high enough to pick out each region, general connectivity betweenconformations can be studied via the connectivity of layers on a graph of reasonablesize.8.1.5 Metrics At Infinite ResolutionsIn the previous sections, we assumed that 픾 and 픾′ were similar, but still bornfrom distinct chain parametrizations. An alternative is to assume that 픾 and 픾′ fol-low from the same parametrization but exist at different resolutions. Applying met-rics Ω푉 , Ω, and Ω to different resolutions of the same parametrizations allowsus to estimate the impact that increased sampling resolution has on conformationspace approximations. In fact,Ω퐴∗ is such an estimation, since it’s essentially com-paring some conformation graph 픾, which exists at a finite resolution, with what itshould be at infinite resolution.Definition 8.11 (Reflexive Congruence Metrics). Let 픾푖 be generated at resolution푟푖 =< 푖, 푖, 푖, 푖, 푖, 푖 > for some chain parametrization. Then Ω푉 (픾푖,픾푗), Ω(픾푖,픾푗),and Ω(픾푖,픾푗) are reflexive congruent metrics. If 푗 = 푖+ 1 or 푖 = 푗 + 1, then theyare step-wise reflexive.If conformation graphs are generated iteratively through increasing resolutionsof 푛푐 = 푛푒, we can produce, for any single parametrization, a vector of four valueswhich measure how accurate the approximations are.43This follows from the proof of Theorem 7.2. For every non-boundary point 푦푝 ∈ 푌 , there is anopen 푚-ball centered on 푦푝 that doesn’t contain boundary points. It follows then that every connectedcomponent in 푌 −퐵, or region in 푌 , has a non-trivial extent. As푋 is of finite size, being the productfinite intervals [0◦, 360◦), so too must 푌 be a finite푚-manifold. Thus there can only be a finite numberof regions. By assumption, stacked graphs only involve finite IK solutions, so that every region hasfinitely manly layers. Therefore both the number of regions and layers in any chain conformationspace are finite.1098.1. Comparing Normalized WorkspacesDefinition 8.12 (Reflexive Congruence Vector). Let 픾푖 and 픾푖+1 be stacked latticegraphs associated with a single chain parametrization with resolution푟푖 =< 푖, 푖, 푖, 푖, 푖, 푖 > . (8.18)If the weightings of Ω and Ω are such thatlim푖→∞Ω(픾푖,픾푖+1) = 1 (8.19)lim푖→∞Ω(픾푖,픾푖+1) = 1, (8.20)then the step-wise reflexive congruence vector isΩ(픾푖) ∶=⟨Ω퐴∗(픾푖),Ω퐴∗(픾푖+1),Ω(픾푖,픾푖+1),Ω(픾푖,픾푖+1)⟩ (8.21)and the total step-wise reflexive congruence metric isΩ픾푖 ∶=3∑푗=0Ω(픾푖)[푗]4(8.22)where Ω픾푖 → 1 as 푖→∞.With the advent of additional reflexive congruence metrics, the definitions ofΩ(픾푖) and Ω픾푖 can be extended to accommodate them.8.1.6 Metrics on Groups of Conformation GraphsΩ퐴∗ ,Ω푉 ,Ω, andΩ can be applied pair-wise to collections of similar stackedgraphs in order to determine how chain parametrizations impact conformation spacegeometry.Definition 8.13 (Collective Congruence Metrics). Let 픊 be a set of 푚 similarstacked graphs 픾푖. The collective 퐴∗, vertex stack, regional, and layer congru-ence metrics Ω퐶퐴∗ ,Ω퐶푉 ,Ω퐶, and Ω퐶 , respectively, are defined as the mean value ofapplying Ω퐴∗ to every 픾푖 ∈ 픊, and Ω푉 ,Ω, and Ω to every pair 픾푖,픾푗 ∈ 픊,respectively. For exampleΩ퐶푉 (픊) ∶=∑픾푖∈픊∑픾푗∈픊,푖≠푗Ω푉 (픾푖,픾푗)(푚2) . (8.23)The collective congruence vector isΩ퐶 (픊) ∶=⟨Ω퐶퐴∗(픊),Ω퐶푉 (픊),Ω퐶(픊),Ω퐶(픊)⟩ (8.24)1108.1. Comparing Normalized Workspaceswhile the total collective congruence metric isΩ퐶픊 ∶=3∑푗=0Ω퐶 (픊)[푗]4. (8.25)In the case of RNA, the stacked graphs 픾푖 ∈ 픊 are parametrized by valuespulled from the distribution of backbone bond length and angle values (Tables 6.1and 6.2). As |픊|→∞, we may find that the values of Ω퐶퐴∗ , Ω퐶푉 , Ω퐶, and Ω퐶 con-verge to particular values. These values would represent the degree to which chainflexibility impacts conformation space geometry. More flexible chains, defined bywider parameter distributions, should have lower values than less flexible chains,defined by narrower distributions.A variant of collective congruence metrics are the mean congruence metrics,which measure how strongly conformation graphs generated by parameter distribu-tions diverge from that generated by mean values.Definition 8.14 (Mean Congruence Metrics). Let 픊 be a set of 푛 similar stackedgraphs 픾푖 generated from a set of chain parameter distributions, where 픾0 is gen-erated from the mean values. The mean 퐴∗ congruence metric isΩ푀퐴∗(픊) ∶=푛−1∑푖=1|Ω퐴∗(픾0) − Ω퐴∗(픾푖)|푛 − 1(8.26)while the mean vertex stack, regional, and layer congruence metrics Ω푀푉 ,Ω푀 , andΩ푀 , respectively, are of the formΩ푀푉 (픊) ∶=푛−1∑푖=1Ω푉 (픾0,픾푖)푛 − 1. (8.27)The mean congruence vector isΩ푀 (픊) ∶=⟨Ω푀퐴∗(픊),Ω푀푉 (픊),Ω푀 (픊),Ω푀 (픊)⟩ (8.28)while the total mean congruence metric isΩ푀픊 ∶=3∑푗=0Ω푀 (픊)[푗]4. (8.29)Variant congruence metrics based on median values are also possible.1118.2. Averaged Stacked GraphsMean (and median) congruence metrics are likely to be those most useful forour purposes, being measures of how the conformation space of a kinematic chainis impacted by converting its rigid (mean-/median-valued) components into semi-rigid components.8.2 Averaged Stacked GraphsThe previous section developed a number of metrics for comparing differentstacked graphs and assignments on them. We now turn to averaging a collection ofstacked graphs.Definition 8.15 (Averaged Stacked Graphs). Let 픊 be a set of similar stackedgraphs 픾푖 all at the same resolution 푟 and generated by the same sampling tech-nique. The averaged stacked graph of 픊, denoted by 픾̄, is composed of the vertexstack set ̄ . Vertex stacks 푉̄푘 ∈ ̄ are the set of vertices 푣̄푘푗 returned by a represen-tative function 푓 acting on the set{푣푝푗 |푣푝푗 ∈ 푉푝 ∈ 픾푖 ∈ 픊 ∋ Norm(푉푝) = Norm(푉푘), ∀푝, 푖}, (8.30)or the set of all vertices 푣푝푗 across all 픾푖 whose containing vertex stacks have thesame normal coordinates as 푉푘. Each element in 푣̄푘푗 ∈ 푉̄푘 is a representative vertex.A representative function is one that either a) selects from a set of vertices asub-set that represents the distribution of sample torsion vectors 푠푘푗 associated withthe vertex set, or b) creates a new, smaller set of vertices with representative sampletorsion vectors.Edges stack 퐸̄푝푞 exists if 푉̄푝 and 푉̄푞 are adjacent in some 픾푖 ∈ 픊.A common class of representative functions would be clustering algorithms,which aggregate sub-sets of vertices into groups based on their associated sampletorsion angles. A set of representative vertices would be formed by either a singlevertex drawn from each group or a single vertex created from each group whose tor-sion angles are some statistical average of its group. Detailed discussion of possiblerepresentative functions is beyond the scope of this work.In the context of kinematic chains and phosphate backbones, 픾̄ describes a con-formation space for a rigid chain containing the key characteristics of a semi-rigidchain. This rigid chain is not necessarily the rigid chain generated by mean valuedchain parameters, whose conformation graph is픾0 (Definition 8.14). By subjecting픾0 and 픾̄ to congruence analysis, we can determine how well a rigid, mean valuedconformation space models, ‘on average’, a semi-rigid conformation space, for agiven set of representative functions1128.3. Energetics and SimulationsThe benefit of using averaged stacked graphs over a collection 픊 is that onlytwo optimal assignments need to be found, one each for 픾0 and 픾̄. In the previ-ous section, comparing a collection of stacked graphs 픊 required, depending onthe metric used, finding feasible/optimal assignments 퐴푖 for every 픾푖 ∈ 픊, in ad-dition to the already time-intensive inverse kinematic sampling process (Chapter6). Whereas a complete analysis of even a small sized 픊 may not be practical, anaverage comparison almost certainly is.Finally, it’s likely possible to generalize averaged stacked graphs so that each픾푖 ∈ 픊 need not be at the same resolution.8.3 Energetics and SimulationsFor any single conformation graph픾with feasible assignment퐴,퐴(픾) is a non-stacked graph on which simulations can be carried out using random processes.These processes require some kind of decision making variable. For phosphatebackbones, the variables are driven by atomic forces.Molecular energetics, the attractive and repulsive forces between atoms, pro-vides ameans of converting our conformation graphs퐴(픾) into digraphs andMarkovchains. As each 퐴(픾) is an approximation of some conformation space, or, in thecase of 퐴̄(퐺̄), an averaged approximation, any energetics model we incorporateneed only be reasonably accurate. We do not need highly accurate quantum me-chanical descriptions of inter-atomic forces as the approximate nature of our graphswill likely override the energetic precision such descriptions would provide. We cansatisfy ourselves with any model that quickly calculates the potential energy con-tained by a single phosphate backbone with torsion angles equal to some solution푠푗푖 . Such a model could simply be the sum total of the Lennard-Jones potential[LMS03] between every pair of atoms in the backbone.Regardless of the specific energetics model used, simulation begins by assign-ing an energetics value 푞푖 to each vertex 푣푖 ∈ 픾44. Next, each edge 푒푖푗 ∈ 픾 isassigned a weight푤푖푗 ∶= 푞푗 − 푞푖. (8.31)All energies can be considered finite, with any infinite or undefined values resultingfrom overlapping atomic nuclei being replaced with sufficiently large numbers. Inaddition, we treat 푒푖푗 and 푒푗푖 as distinct, directed edges so that 푤푖푗 = −푤푗푖.Definition 8.16 (Energized Conformation Graphs). Let 퐴(픾) be a directed confor-mation graph with edge weights representing energy difference between vertices,as described above. Then 퐴(픾) is an energized conformation graph. 퐴(픾)+ is the44Vertex/sample solution energetics are independent of any assignment1138.3. Energetics and Simulationspositive sub-graph consisting of all edges with positive weights, while 퐴(픾)− is thenegative sub-graph consisting of all edges with negative weights.Lemma 8.17. If 퐴(픾) is an energized conformation graph, then 퐴(픾) contains nodirected cycles with all negative edge weights. 퐴(픾)− and 퐴(픾)+ are either treesor forests.Proof. Every vertex has a single, finite, real-valued energy, implying that there isno infinite, repeating sequence of vertices⋯ − 푣0 − 푣1 − 푣2 −⋯ − 푣푛 − 푣0 − 푣1 −… (8.32)whose energies are monotonically decreasing. Therefore there are no directed cy-cles consisting entirely of negative edge weights. Since 퐴(픾)+ is 퐴(픾)− with edgedirections and weight signs reversed, and as퐴(픾)− contains no cycles, neither does퐴(픾)+. Both must therefore be trees or forests.Lemma 8.17 provides a simple way of identifying stable conformations andconformational pathways.Lemma 8.18 (Stable Conformations and Conformational Pathways in퐴(픾)−). Ev-ery leaf in 퐴(픾)−, or vertex with no out-going edges, is a stable conformation andevery directed path is a conformational pathway or conpath.Proof. A conformation is stable if there are no lower energy conformations it canmove into. This is indicated by an outgoing, negative edge. Thus, every leaf in퐴(픾)− is stable as it has no outgoing edges.The existence of multiple directed paths beginning at some vertex 푣푖 ∈ 퐴(픾)−indicates that multiple conpaths are possible. It’s reasonable to assume that thepaths actual phosphate backbones will take are the most energetically favourable(i.e. minimally weighted) edges at each branching point. Still, it’s possible thatless than optimal, though still negative, paths are chosen, perhaps do to atomicforces external to the backbone interacting with it. Path-choice can be modelledprobabilistically by replacing each edge weight 푤푖푗 with the proportional value푤̃푖푗 ∶=푞푗 − 푞푖∑푘∶푒푖푘∈퐴(픾)−(푞푘 − 푞푖)(8.33)with 푤̃푖푖 ∶= 1 when there are no outgoing edges from 푣푖.Probabilistic forms of energized 퐴(픾)− have a useful property.1148.4. Model Validation and Real-World DataTheorem 8.19. Probabilistic, energized 퐴(픾)− are absorbing Markov chains 45.Proof. The definition of 푤̃푖푗 implies that 퐴(픾)− is a Markov chain as the sum ofall edge weights leaving any 푣푖 is 1. That 퐴(픾)− is absorbing is implied by Lemma8.17: every conpath eventually ends in a stable conformation, which is an absorbingstate.The calculation for determining the probability that any path starting at 푣푖 willend at any particular absorbing state is well known for absorbing Markov chains[TK98]. Given the torsion angles for some initial RNA conformation and a prob-abilistic conformation graph 퐴(픾)−, we can therefore predict which final confor-mation it is most likely to stabilize at, up to the resolution of 퐴(픾)−. This appliesequally to rigid, mean valued conformations graphs 퐴(픾0), semi-rigid, averagedconformation graphs 퐴(픾̄), and collections of conformation graphs 픊 with theirassociated assignments. In the third case, the long-term behaviour of each 퐴(픾푖)Markov chain is calculated and compared.Additional analysis techniques can be used to identify which vertices contributemost to these probabilities. The implication is that these vertices are conformationalbottlenecks, which are precisely those conformations that would be targeted for drugdevelopment (Chapter 1).It’s possible to study pathways on an energized conformation graph withoutremoving 퐴(픾)+. To account for energetic fluctuation in a backbones environment,a random value can be add or subtracted from each conformation’s energy after eachmovement on the graph. While complicating the analysis, it may help to illuminatetransient pathways, pathways which, on average, are only mildly unfavourable do toslightly positive edge weight values. Edges in 퐴(픾)+ which are close to zero mayprovide occasional energetically favourable pathways which would circumvent theeffects of conformation-targeting drugs.8.4 Model Validation and Real-World DataOne way to validate our model is to compare the predicted distributions of con-formations using absorbing Markov chains against real-world data, such as the Nu-cleic Acid Database’s massive collection of RNA crystallography data. At the timeof this writing, the online database consists of over 1100 pure RNA structures,some composed of several hundred nucleotides, with each nucleotide representing45A Markov chain is absorbing if there is at least one absorbing state (i.e. a state where the proba-bility of leaving it is 0) and every state can reach an absorbing state [TK98].1158.4. Model Validation and Real-World Data(a)(b)Figure 8.3: Sample names of real-world data (blue circles) are assigned new namesand coordinates to match the theoretical sample (black circles) contained by thehalf-open lattice interval the real-world data falls in. These intervals are basedon the lattice’s resolution. For the cartesian case (a) with 푛푐 = 2, a real-worlddata point with normal coordinate −0.489 would be labelled 3 with coordinate −12 .In the eulerian case (b) with 푛푒 = 2, 348.9◦ would be labelled as sample 0 withcoordinate 0◦.a stable conformation46. Unfortunately, NDB’s RNA data does not come ready-packaged with normalized chain parametrizations. Each nucleotide needs to beprocessed. The process of converting raw NDB data into an appropriate chain for-mat is a technical exercise we’ll not undertake here. For our purposes we’ll assumethat any real-world conformation data we have access to is in such a format.There is also the issue that real-world chains involve real-valuedworkplace sam-pling locations which do not fit nicely on the vertices of our sampling lattices (Chap-ter 6). This problem can be resolved by grouping data based on lattice resolution.Figure 8.3 illustrates one such grouping technique.A small difficulty arises when we consider that there are two related sets of val-46Though not necessarily energetically favourable. See below.1168.4. Model Validation and Real-World Dataues: euclidean sample names and torsion angles. Recall that every euclidean sam-ple corresponds to a specific set of torsion angles, or inverse kinematic solutions(Sections 5.2 and 6.2). However we group real-world data on our sampling lattices,the correspondence needs to be consistent: if a data point is grouped with sample푆6, then its associated torsion angles need to be sufficiently close to some solution푠6푖 . What constitutes ‘sufficiently close’ is debatable, but for averaged conforma-tion graphs, within two standard deviations of the averaged solutions’ distributionshould suffice.Assume, then, that we have both a technique for grouping data as well as amethod for ensuring consistent correspondence between sample grouping and sam-ple solutions. Comparing model predictions with real-world data amounts to count-ing the number of real-world data points existing in each lattice grouping, findingthe proportion of all counts in each group, and comparing these proportions to thelong term behaviour of our absorbing Markov chains. If our model is accurate, theproportions should be similar. If not, something may be amiss.There is a hidden assumption we’re making in this comparison which is thatreal-world data is energetically favourable. If we find that a large proportion ofthese nucleotides exist in conformations which we predict to be unstable, then itneed not mean our approach is flawed. Recall that we’re modelling a single nu-cleotide backbone in isolation of its nucleoside (Chapter 1). Additional energeticsare involved with stacking and base pairing of nucleosides in polynucleotides whichmay force individual backbones into unstable conformations while maintaining anoverall energetically favourable conformation for an entire strand.A second validation technique is to compare the conformational pathways ofenergized conformation graphs with those produced by other, more sophisticatedmolecular modelling software, ones wherein detailed energetics calculations areused. Existing software is computationally expensive47. Should stacked graphsand assignments provide similar, though perhaps less accurate, results than othertechniques at a fraction of the time, the former could be used to guided simulationson the latter. Kinematic simplification of transition structures may prove useful toforce field algorithms by way of providing ranges of probable conformations.47Based on discussions with Al Vasius117Chapter 9Concluding Remarks and FutureResearchThe aim of this thesis has been to develop a technique for studying how nucleicacids move, in particular, ribonucleic acid. Three research goals were outlined inChapter 1 which were formally met in Chapter 81. The approximation of conformation spaces for semi-rigid kinematic chains,in the form of optimal assignments on averaged stacked graphs;2. The identification of energetically favourable backbone conformations, in theform of absorbing states in Markov chains;3. The identification of energetically favourable conformational pathways, inthe form of directed paths on negative energized conformation graphs퐴(픾)−.It was in the chapters that preceded it, however, that the goals were substantively de-veloped. The technique was developed conceptually, if not entirely chronologically,as follows. We began by restricting our attention to the phosphate backbone of asingle nucleotide as it provides the lowest level restrictions on movement. The fullrange of motion for a single backbone was viewed as a pre-image problem, namely,finding an approximation to 푄−1 where 푄 is continuous (Equation 5.3) and formsa connected manifold [McC90]. To do this, we took advantage of the existence ofhigh-speed algorithms for finding the inverse kinematics of 6푅 kinematic chains[MC94], which a single backbone can be modelled as, to sample 푄−1. These sam-ples were ‘stitched together’ to produce stacked graphs, on which optimal feasibleassignments formed the approximations of 푄−1. Finally, we developed a numberof metrics for investigating the accuracy of the approximation, generalized approx-imations to account for semi-rigid nature of phosphate backbones, and convertedthe approximations into absorbing Markov chains to find stable conformations andconformational pathways.The end result is a graph 퐴(픾) on which walks form a sequence of conforma-tional changes in a single phosphate backbone; small, discrete changes in torsionangles that approximate continuous motion. Determining whether one backbone118Chapter 9. Concluding Remarks and Future Researchconformation can be reached from another conformation is reduced to finding alow energy path between two vertices. While there nevertheless exist computa-tional barriers to be overcome, namely that of finding large numbers of IK solutionsand solving collections of linear programs, the computational burden is all upfront:once solutions and assignments have been found, the actual process of finding path-ways is straightforward.There remains, of course, the issue of validation. This refers not solely towhether the technique presented above performs as required - namely, whetherapproximations to the conformation problem can be produced with a reasonabledegree of accuracy - but also whether those approximations can be had within areasonable period of time. The computational requirements for producing high res-olution maps of a single phosphate backbone conformation space are dependent onboth the speed of inverse kinematic algorithms (Section 6.1) and on the formulationof feasibility algorithms, such as that outlined in Chapter 4. Fortunately, the natureof the technique is less restricted in terms of production than theory. Assumingthat, practically, useful approximations to the conformation space can be had, theissue of timely production is of limited import. The nature of the technique allowsfor improvements to be had over a period of time. Samples can gradually be addedand optimal assignments found quickly on local regions. While local optimizationis may not yield global optimality (Section 4.1 and Figure 4.5), actual globally opti-mal assignments are not necessarily necessary, as we noted in the previous chapter.We know what an optimal feasible assignment looks like with a sufficiently largenumber of samples - the 퐴∗ congruence metric Ω퐴∗ (Section 8.1.1). What willlikely be of most interest in conformation spaces are the areas near singular bound-aries, specifically, the connectivity between layers of distinct regions. Regions andlayers are themselves dull structures, uniform regions of space that may very wellbe represented by single vertex stacks48. Once singular boundaries have been delin-eated at a particular sampling resolution, further approximation improvements willalmost certainly take the form of increased sampling along these boundaries to re-fine them. Rather then improving global resolution, restricted, local improvementsshould greatly reduce overall computational burdens.With regards to future research beyond that of model validation, there exists atleast one other application for stacked graphs. During its development, I discoveredthat it can also be used for modelling certain kinds of object tracking problems,which could be explored. There is also the relationship between stacked graphsand symmetric groups which is in need of additional investigation, having onlybeen briefly considered here. It is unknown whether there exist other symmetricgroup problems which can benefit from a graph dual interpretation. The issue of48Hence regional stacked graphs ℝ픾 (Definition 2.35).119Chapter 9. Concluding Remarks and Future Researchimproving the computational complexity of solving the assignment feasibility prob-lem could also be addressed.Finally, I think it important to note that the approach we’ve taken to address theconformation problem appears to be a novel one and is, at least conceptually, fairlystraightforward. While a diverse range of mathematical knowledge is required tounderstand and develop it, the technical depth required of each field is limited. Thegraph theory component (Chapter 2) is elementary, as is the group theory (Chap-ter 3). Linear programming (Chapter 4), while necessary to find (optimal) feasibleassignments, it is not required to determine necessary and sufficient conditions forfeasibility (Theorem 2.31). Kinematic chains are used casually. What we requirefrom them is the boundedness of the number of inverse kinematic solutions for ourparticular chain [Ang07], the existence of high speed algorithms to find these solu-tions [MC94], and the knowledge that they are continuous functions that producemanifolds [McC90]. Even the topological connection between stacked graphs andthe conformation space problem (Chapter 7) is fundamental.This is said not to discourage the technique. At its core, the complex issue ofhow to approximate the conformation space of a nucleic acid backbone has been re-duced to solving a collection of interrelated assignment problems, problems whichare well-know and simple to understand. That it can be done with a suite of seem-ingly mundane mathematics is, I believe, worthy of attention. Nearly every mathe-matical course I’ve taken as both an undergraduate and graduate student has directlycontributed to the production of this thesis.There is a scene early in Dumas’ ‘The Count ofMonte Cristo’ [Dum45] whereinEdmond Dantès, a prisoner of the Château d’If, is conversing with abbé Faria, an-other prisoner, in the former’s cell. Dantès, awed by Faria’s breadth of reading,remarks that the abbé must know many languages, to which Faria responds that heknows several and that:‘... I can [also] understand modern Greek with the help of AncientGreek, but I speak it poorly; I am studying it now.’‘You are studying it?’ Dantès exclaimed.‘Yes, I have compiled a vocabulary of the words that I know and havearranged them, combined them, turned them one way, then the other,so as to make them sufficient to express my thoughts. I know aboutone thousand words, which is all I absolutely need, though I believethere are a hundred thousand in dictionaries. Of course I shall notbe a polished speaker, but I shall make myself understood perfectly,which is good enough.’I would be a poor student if I claimed that I knew all I absolutely needed and Ican only hope that this work is as clear to others as it is to myself.120Bibliography[AMO93] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory,Algorithms, and Applications. Prentice Hall, New Jersey, 1993. →pages 9, 20, 21, 29, 30, 56, 57, 59[Ang07] J. Angeles. Fundamentals of Robot Mechanical Systems: Theory,Methods, and Algorithms, 3rd Edition. Mechanical Engineering Se-ries. Springer, 2007. → pages 2, 68, 69, 70, 71, 72, 104, 120[BHA15] M.P. Blakely, S.S. Hasnain, and S.V. Antonyuk. Sub-atomic reso-lution x-ray crystallography and neutron crystallography: Promise,challenges and potential. IUCrJ, 2(4):464–474, 2015. → pages 82[Bol79] B. Bollobas. Graph Theory: An Introductory Course. Springer-Verlag, 1979. → pages 13, 29[BW97] A.S. Brodsky and J.R. Williamson. Solution structure of the hiv-2 tar-argininamide complex. J. Mol. Biol., 267(3):624–639, 1997. → pages5, 6[Dat16] Nucleic Acid Database. Ideal geometries [online]. 2016 [cited Febru-ary 27, 2016]. → pages 2, 5, 79[Dum45] A. Dumas. The Count of Monte Cristo. Penguin Classics, 1844-45.→ pages 120[Fou92] L.R. Foulds. Graph Theory Applications. Springer, 1992. → pages9, 40[Fra03] J.B. Fraleigh. A First Course in Abstract Algebra, 7th Edition. Addi-son Wesley, 2003. → pages 39, 40, 42[GSC+96] A. Gelbin, B. Schneider, L. Clowney, S. Hsieh, OlsonW.K., and H.M.Berman. Geometric parameters in nucleic acids: Sugar and phosphateconstituents. J. Am. Chem. Soc., 118(3):519–529, 1996. → pages 79,80121Bibliography[KHP11] K. S. Keating, E.L. Humphris, and A.M. Pyle. A new way to see rna.Quarterly Reviews of Biophysics, 44(4):433–466, 2011. → pages 1, 2[LMS03] K.J. Laidler, J.H. Meiser, and B.C. Sanctuary. Physical Chemistry,Fourth Edition. Houghton Mifflin, 2003. → pages 113[LNC93] A.L. Lehninger, D.L. Nelson, and M.M. Cox. Principles of Biochem-istry, 2nd Edition. Worth, 1993. → pages 1, 3[Mak08] C.H. Mak. Rna conformational sampling. i. single-nucleotide loopclosure. J. Comput. Chem., 29(6):926–933, 2008. → pages 1, 2, 4[MC94] D. Manocha and J.F. Canny. Efficient inverse kinematics for gen-eral 6r manipulators. IEEE Transactions on Robotics and Automaton,10(5):648–657, 1994. → pages 4, 73, 82, 118, 120[McC90] J.M. McCarthy. An Introduction to Theoretical Kinematics. The MITPress, 1990. → pages 68, 69, 95, 118, 120[MCM11] C.H. Mak, W.Y Chung, and N.D. Markovskiy. Rna conformationalsampling. ii. arbitrary length multinucleotide loop closure. J. Chem.Theory Comput., 7:1198–1207, 2011. → pages 2[MLL08] R.J. Milgram, G. Liu, and J.C. Latombe. On the structure of the in-verse kinematics map of a fragment of protein backbone. J. Comput.Chem., 29(1):50–68, 2008. → pages 1, 4[Mun00] J.R. Munkres. Topology, 2nd Edition. Prentice Hall, 2000. → pages95[PRT+07] J.M. Porta, L. Ros, F. Thomas, F. Corcho, J. Cantó, and J.J. Pérez.Complete maps of molecular-loop conformation spaces. J. Comput.Chem., 28(13):2170–2189, 2007. → pages 2, 4[Rom12] S. Roman. Fundamentals of Group Theory: An Advanced Approach.SpringerLink, 2012. → pages 45[TK98] H.M. Taylor and S. Karlin. An Introduction to Stochastic Modelling,3rd Edition. Academic Press, 1998. → pages 115[WKM+08] X. Wang, G. Kapral, L. Murray, D. Richardson, J. Richardson, andJ. Snoeyink. Rnabc: Forward kinematics to reduce all-atom stericclashes in rna backbone. J. Math. Biol., 56:253–278, 2008. → pages1, 2122Appendices123Appendix AConstructing Unique SubscriptsIn the one dimensional case, where the name of any sample 푆푟 is < 푘 >, thensetting 푟 = 푘 is sufficient to provide a unique sample subscript. In higher dimen-sions, unique integral subscripts depend on the number of dimensions or length, of푆푟. On way to create integral subscripts is via ‘spiralling’. Figure A.1 demonstratesthe process in the two-dimensional cartesian case. Higher dimensions with euleriancomponents are similarly constructed.Table A.1 lists the first twenty-eight sample names generated from unique sub-scripts, in accordance with the process in Figure A.1.Table A.1: The first 27 samples with unique subscripts generated for the two-dimensional cartesian case using a spiralling technique.Sample Name Sample Name푆0 < 0, 0 > 푆14 <12 ,12 >푆1 < −1, 0 > 푆15 < 0,12 >푆2 < −1,−1 > 푆16 < −12 ,12 >푆3 < 0,−1 > 푆17 < −1,12 >푆4 < 1,−1 > 푆18 < −1,−12 >푆5 < 1, 0 > 푆19 < −12 ,−1 >푆6 < 1, 1 > 푆20 <12 ,−1 >푆7 < 0, 1 > 푆21 < 1,−12 >푆8 < −1, 1 > 푆22 < 1,12 >푆9 < −12 , 0 > 푆23 <12 , 1 >푆10 < −12 ,−12 > 푆24 < −12 , 1 >푆11 < 0,−12 > 푆25 < −14 , 0 >푆12 <12 ,−12 > 푆26 < −14 ,−14 >푆13 <12 , 0 > 푆27 < 0,−14 >124Appendix A. Constructing Unique Subscripts‘Spiral integral’ construction resembles the bisection technique for sample names(Figure 6.3). The pattern can spiral in or out, clockwise or counter-clockwise, andgenerates all subscripts for samples at and above a given resolution.As this work does not define each sample푆푟 by unique subscripts, but instead byits name (Definition 6.3), and as there are a variety of spiralling patterns, an explicitalgorithm for finding spiral integers based on sample names is not included.125Appendix A. Constructing Unique Subscripts(a) Lattice for 푛푐0 = 푛푐1 = 0 and 1 (b) Lattice for 푛푐0 = 푛푐1 = 2(c) Lattice for 푛푐0 = 푛푐1 = 3Figure A.1: One method for spiral integer construction on the square [−1, 1]2generated by 푛푐0 and 푛푐1 . Coordinates correspond to sample names (see Figure6.3). (a) Beginning at the origin (black circle) and with counter-clockwise rota-tion, follow the red arrows to visit each sample generated by 푛푐0 = 푛푐1 = 0 (redvertices) and 1, labelling them by increasing integers with 0 for the origin (labelssuppressed). Labels form the unique subscript values. (b) Add the samples gener-ated by 푛푐0 = 푛푐1 = 2. The next label corresponds to the sample immediately leftof the origin. Repeat step (a), labelling samples in a counter-clockwise direction,spiralling outwards. Vertices and arrows indicated in blue are those generated byprevious values of 푛푐0 and 푛푐1 . (c) Repeat step (b) with 푛푐0 = 푛푐1 = 3. Only the firstfew red arrows are shown for readability.126Appendix BConstructing NormalCoordinatesWe begin with the cartesian case, followed by the eulerian case, both in onedimension. The higher dimensional cases are cartesian products of the single di-mensional cases. The aim is to assign each sample a rational sort value 푝푞∈ [0, 1]in the cartesian case so that samples form a partially ordered set. The sort valuesare then transformed into normal coordinates in [−1, 1]. In the eulerian case, therational sort value is in [0, 1) with a normal coordinate value of [0, 360◦)Assume that sample 푆푟 is generated by 푛푐 > 0. The denominator 푞 of its sortvalue is defined to be one less than the total number of samples generated by 푛푐bisections. From Table 6.4, 푛푐 = 0 generates two samples, with each incrementof 푛푐 increases the number of solutions by a power of two. The total number ofsamples generated by 푛푐 bisections is푞 = (2 + 20 + 21 +⋯ + 2푛푐−1) − 1 (B.1)= 1 +푛푐−1∑푖=02푖 (B.2)= 1 + 1 − 2푛푐1 − 2(B.3)= 2푛푐 . (B.4)The numerator 푝 of the sort value for 푆푟 is the number of ‘ticks’ from the left-hand side that 푆푟 is located at in Figure 6.3. For example, if 푛푐 = 2, then 푝 = 1 forsample 3 and 푝 = 3 for sample 4.According to Table 6.3, the last label generated by (푛푐 − 1) is2푛푐−1so that if the sample name of 푆푟 is 푘, then 푘 is the푘 − 2푛푐−1 (B.5)sample name generated by 푛푐 bisections. Thus, label 2푛푐−1+1 should be at the firstposition, 2푛푐−1 + 2 should be at the second, etc. However, labels generated by 푛푐127Appendix B. Constructing Normal Coordinateshave positions which alternate with those generated by (푛푐 − 1), so that the formerlabels have even 푝 values and the later have odd ones. This implies that푝 = 2(푘 − 2푛푐−1) − 1= 2푘 − 2푛푐 − 1. (B.6)The rational sort value 푝푞for 푆푟 is therefore푝푞= 2푘 − 2푛푐 − 12푛푐= 2푘 − 12푛푐− 1 (B.7)when 푛푐 > 0. For 푛푐 = 0, there are only two samples, which are always at theend-points of the interval. We therefore define 푝 ∶= 0 and 푝 ∶= 1 for 푘 = 0 and푘 = 1, respectively, giving rational sort values of 0 and 1 for 푆푟 with names 푘 = 0and 푘 = 1, respectively.Conversion of rational sort values to normal coordinates is accomplished bytransforming [0, 1] into [−1, 1]푝푞∗ 2 − 1 =(2푘 − 12푛푐− 1)∗ 2 − 1= 2푘 − 12푛푐−1− 3. (B.8)Rational sort values 푝′푞′for eulerian components are generated in a manner sim-ilar to that above. If 푆푟 has name 푘′ and is generated by 푛푒 > 0, then 푞′ is푞′ =푛푒−1∑푖=02푖 (B.9)= 1 − 2푛푒1 − 2(B.10)= 2푛푒 − 1 (B.11)as only one sample is generated by 푛푒 = 0. The numerator remains the same at푝′ = 2푘′ − 2푛푒 − 1 (B.12)yielding a rational sort value of푝′푞′= 2푘′ − 2푛푒 − 12푛푐 − 1(B.13)= 2푘′2푛푒 − 1− 1 (B.14)128Appendix B. Constructing Normal Coordinatesfor 푛푒 > 0. As with the cartesian components, for푆푟 with name 푘′ = 0 generated by푛푒 = 0, the rational sort value is defined to be 0. This produces rational sort valuesin [0, 1). Normal coordinates are formed by transforming [0, 1) into [0◦, 360◦)푝′푞′∗ 360◦ =(2푘′2푛푒 − 1− 1)∗ 360◦ (B.15)In the general case of sample푆푘 = ⟨푘0, 푘1, 푘2, 푘3, 푘4, 푘5⟩with resolutionRes(푆푘) =⟨푛푐0 , 푛푐1 , 푛푐2 , 푛푒0 , 푛푒1 , 푛푒2⟩we have the following construction for function Norm(⋅) (Definition 6.4)Norm(푆푘) = ⟨푤0, 푤1, 푤2, 푤3, 푤4, 푤5⟩where푤0 =2푘0−12푛푐0−1− 3, 푤1 =(2푘′32푛푒0 − 1− 1)∗ 360◦ (B.16)푤2 =2푘1−12푛푐1−1− 3, 푤3 =(2푘42푛푒1 − 1− 1)∗ 360◦푤4 =2푘2−12푛푐2−1− 3, 푤5 =( 2푘52푛푒2 − 1− 1)∗ 360◦.129


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items