--- /dev/null
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml">
+<head>
+<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
+<meta http-equiv="X-UA-Compatible" content="IE=9"/>
+<title>RNAlib-2.1.2: Parsing and Comparing - Functions to Manipulate Structures</title>
+<link href="tabs.css" rel="stylesheet" type="text/css"/>
+<script type="text/javascript" src="jquery.js"></script>
+<script type="text/javascript" src="dynsections.js"></script>
+<link href="navtree.css" rel="stylesheet" type="text/css"/>
+<script type="text/javascript" src="resize.js"></script>
+<script type="text/javascript" src="navtree.js"></script>
+<script type="text/javascript">
+ $(document).ready(initResizable);
+</script>
+<link href="doxygen.css" rel="stylesheet" type="text/css" />
+</head>
+<body>
+<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
+<div id="titlearea">
+<table cellspacing="0" cellpadding="0">
+ <tbody>
+ <tr style="height: 56px;">
+ <td style="padding-left: 0.5em;">
+ <div id="projectname">RNAlib-2.1.2
+ </div>
+ </td>
+ </tr>
+ </tbody>
+</table>
+</div>
+<!-- end header part -->
+<!-- Generated by Doxygen 1.8.1.1 -->
+ <div id="navrow1" class="tabs">
+ <ul class="tablist">
+ <li><a href="index.html"><span>Main Page</span></a></li>
+ <li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
+ <li><a href="modules.html"><span>Modules</span></a></li>
+ <li><a href="annotated.html"><span>Data Structures</span></a></li>
+ <li><a href="files.html"><span>Files</span></a></li>
+ </ul>
+ </div>
+</div><!-- top -->
+<div id="side-nav" class="ui-resizable side-nav-resizable">
+ <div id="nav-tree">
+ <div id="nav-tree-contents">
+ </div>
+ </div>
+ <div id="splitbar" style="-moz-user-select:none;"
+ class="ui-resizable-handle">
+ </div>
+</div>
+<script type="text/javascript">
+$(document).ready(function(){initNavTree('mp_parse.html','');});
+</script>
+<div id="doc-content">
+<div class="header">
+ <div class="headertitle">
+<div class="title">Parsing and Comparing - Functions to Manipulate Structures </div> </div>
+</div><!--header-->
+<div class="contents">
+<div class="textblock"><h2>Representations of Secondary Structures</h2>
+<p>The standard representation of a secondary structure is the <em>bracket notation</em>, where matching brackets symbolize base pairs and unpaired bases are shown as dots. Alternatively, one may use two types of node labels, 'P' for paired and 'U' for unpaired; a dot is then replaced by '(U)', and each closed bracket is assigned an additional identifier 'P'. We call this the expanded notation. In <a class="el" href="citelist.html#CITEREF_fontana:1993b">[3]</a> a condensed representation of the secondary structure is proposed, the so-called homeomorphically irreducible tree (HIT) representation. Here a stack is represented as a single pair of matching brackets labeled 'P' and weighted by the number of base pairs. Correspondingly, a contiguous strain of unpaired bases is shown as one pair of matching brackets labeled 'U' and weighted by its length. Generally any string consisting of matching brackets and identifiers is equivalent to a plane tree with as many different types of nodes as there are identifiers.</p>
+<p>Bruce Shapiro proposed a coarse grained representation <a class="el" href="citelist.html#CITEREF_shapiro:1988">[12]</a>, which, does not retain the full information of the secondary structure. He represents the different structure elements by single matching brackets and labels them as 'H' (hairpin loop), 'I' (interior loop), 'B' (bulge), 'M' (multi-loop), and 'S' (stack). We extend his alphabet by an extra letter for external elements 'E'. Again these identifiers may be followed by a weight corresponding to the number of unpaired bases or base pairs in the structure element. All tree representations (except for the dot-bracket form) can be encapsulated into a virtual root (labeled 'R'), see the example below.</p>
+<p>The following example illustrates the different linear tree representations used by the package. All lines show the same secondary structure.</p>
+<pre class="fragment">a) .((((..(((...)))..((..)))).)).
+ (U)(((((U)(U)((((U)(U)(U)P)P)P)(U)(U)(((U)(U)P)P)P)P)(U)P)P)(U)
+b) (U)(((U2)((U3)P3)(U2)((U2)P2)P2)(U)P2)(U)
+c) (((H)(H)M)B)
+ ((((((H)S)((H)S)M)S)B)S)
+ (((((((H)S)((H)S)M)S)B)S)E)
+d) ((((((((H3)S3)((H2)S2)M4)S2)B1)S2)E2)R)
+</pre><p>Above: <a class="el" href="structTree.html">Tree</a> representations of secondary structures. a) Full structure: the first line shows the more convenient condensed notation which is used by our programs; the second line shows the rather clumsy expanded notation for completeness, b) HIT structure, c) different versions of coarse grained structures: the second line is exactly Shapiro's representation, the first line is obtained by neglecting the stems. Since each loop is closed by a unique stem, these two lines are equivalent. The third line is an extension taking into account also the external digits. d) weighted coarse structure, this time including the virtual root.</p>
+<p>For the output of aligned structures from string editing, different representations are needed, where we put the label on both sides. The above examples for tree representations would then look like:</p>
+<pre class="fragment">a) (UU)(P(P(P(P(UU)(UU)(P(P(P(UU)(UU)(UU)P)P)P)(UU)(UU)(P(P(UU)(U...
+b) (UU)(P2(P2(U2U2)(P2(U3U3)P3)(U2U2)(P2(U2U2)P2)P2)(UU)P2)(UU)
+c) (B(M(HH)(HH)M)B)
+ (S(B(S(M(S(HH)S)(S(HH)S)M)S)B)S)
+ (E(S(B(S(M(S(HH)S)(S(HH)S)M)S)B)S)E)
+d) (R(E2(S2(B1(S2(M4(S3(H3)S3)((H2)S2)M4)S2)B1)S2)E2)R)
+</pre><p>Aligned structures additionally contain the gap character '_'.</p>
+<h2>Parsing and Coarse Graining of Structures</h2>
+<p>Several functions are provided for parsing structures and converting to different representations.</p>
+<pre class="fragment">char *expand_Full(const char *structure)
+</pre><p> Convert the full structure from bracket notation to the expanded notation including root. </p>
+<pre class="fragment">char *b2HIT (const char *structure)
+</pre><p> Converts the full structure from bracket notation to the HIT notation including root. </p>
+<pre class="fragment">char *b2C (const char *structure)
+</pre><p> Converts the full structure from bracket notation to the a coarse grained notation using the 'H' 'B' 'I' 'M' and 'R' identifiers. </p>
+<pre class="fragment">char *b2Shapiro (const char *structure)
+</pre><p> Converts the full structure from bracket notation to the <em>weighted</em> coarse grained notation using the 'H' 'B' 'I' 'M' 'S' 'E' and 'R' identifiers. </p>
+<pre class="fragment">char *expand_Shapiro (const char *coarse);
+</pre><p> Inserts missing 'S' identifiers in unweighted coarse grained structures as obtained from <a class="el" href="RNAstruct_8h.html#a9c80d92391f2833549a8b6dac92233f0" title="Converts the full structure from bracket notation to the a coarse grained notation using the 'H' 'B' ...">b2C()</a>. </p>
+<pre class="fragment">char *add_root (const char *structure)
+</pre><p> Adds a root to an un-rooted tree in any except bracket notation. </p>
+<pre class="fragment">char *unexpand_Full (const char *ffull)
+</pre><p> Restores the bracket notation from an expanded full or HIT tree, that is any tree using only identifiers 'U' 'P' and 'R'. </p>
+<pre class="fragment">char *unweight (const char *wcoarse)
+</pre><p> Strip weights from any weighted tree. </p>
+<pre class="fragment">void unexpand_aligned_F (char *align[2])
+</pre><p> Converts two aligned structures in expanded notation. </p>
+<pre class="fragment">void parse_structure (const char *structure)
+</pre><p> Collects a statistic of structure elements of the full structure in bracket notation. </p>
+<dl class="section see"><dt>See also:</dt><dd><a class="el" href="RNAstruct_8h.html" title="Parsing and Coarse Graining of Structures.">RNAstruct.h</a> for prototypes and more detailed description</dd></dl>
+<h2>Distance Measures</h2>
+<p>A simple measure of dissimilarity between secondary structures of equal length is the base pair distance, given by the number of pairs present in only one of the two structures being compared. I.e. the number of base pairs that have to be opened or closed to transform one structure into the other. It is therefore particularly useful for comparing structures on the same sequence. It is implemented by</p>
+<pre class="fragment">int bp_distance(const char *str1,
+ const char *str2)
+</pre> <p>For other cases a distance measure that allows for gaps is preferable. We can define distances between structures as edit distances between trees or their string representations. In the case of string distances this is the same as "sequence alignment". Given a set of edit operations and edit costs, the edit distance is given by the minimum sum of the costs along an edit path converting one object into the other. Edit distances like these always define a metric. The edit operations used by us are insertion, deletion and replacement of nodes. String editing does not pay attention to the matching of brackets, while in tree editing matching brackets represent a single node of the tree. <a class="el" href="structTree.html">Tree</a> editing is therefore usually preferable, although somewhat slower. String edit distances are always smaller or equal to tree edit distances.</p>
+<p>The different level of detail in the structure representations defined above naturally leads to different measures of distance. For full structures we use a cost of 1 for deletion or insertion of an unpaired base and 2 for a base pair. Replacing an unpaired base for a pair incurs a cost of 1.</p>
+<p>Two cost matrices are provided for coarse grained structures:</p>
+<pre class="fragment">/* Null, H, B, I, M, S, E */
+ { 0, 2, 2, 2, 2, 1, 1}, /* Null replaced */
+ { 2, 0, 2, 2, 2, INF, INF}, /* H replaced */
+ { 2, 2, 0, 1, 2, INF, INF}, /* B replaced */
+ { 2, 2, 1, 0, 2, INF, INF}, /* I replaced */
+ { 2, 2, 2, 2, 0, INF, INF}, /* M replaced */
+ { 1, INF, INF, INF, INF, 0, INF}, /* S replaced */
+ { 1, INF, INF, INF, INF, INF, 0}, /* E replaced */
+
+
+/* Null, H, B, I, M, S, E */
+ { 0, 100, 5, 5, 75, 5, 5}, /* Null replaced */
+ { 100, 0, 8, 8, 8, INF, INF}, /* H replaced */
+ { 5, 8, 0, 3, 8, INF, INF}, /* B replaced */
+ { 5, 8, 3, 0, 8, INF, INF}, /* I replaced */
+ { 75, 8, 8, 8, 0, INF, INF}, /* M replaced */
+ { 5, INF, INF, INF, INF, 0, INF}, /* S replaced */
+ { 5, INF, INF, INF, INF, INF, 0}, /* E replaced */
+</pre><p>The lower matrix uses the costs given in <a class="el" href="citelist.html#CITEREF_shapiro:1990">[11]</a>. All distance functions use the following global variables:</p>
+<pre class="fragment">int cost_matrix;
+</pre><p> Specify the cost matrix to be used for distance calculations. </p>
+<pre class="fragment">int edit_backtrack;
+</pre><p> Produce an alignment of the two structures being compared by tracing the editing path giving the minimum distance. </p>
+<pre class="fragment">char *aligned_line[4];
+</pre><p> Contains the two aligned structures after a call to one of the distance functions with <a class="el" href="dist__vars_8h.html#aa03194c513af6b860e7b33e370b82bdb" title="Produce an alignment of the two structures being compared by tracing the editing path giving the mini...">edit_backtrack</a> set to 1. </p>
+<dl class="section see"><dt>See also:</dt><dd><a class="el" href="utils_8h.html" title="Various utility- and helper-functions used throughout the Vienna RNA package.">utils.h</a>, <a class="el" href="dist__vars_8h.html" title="Global variables for Distance-Package.">dist_vars.h</a> and <a class="el" href="stringdist_8h.html" title="Functions for String Alignment.">stringdist.h</a> for more details</dd></dl>
+<h3>Functions for <a class="el" href="structTree.html">Tree</a> Edit Distances</h3>
+<pre class="fragment">Tree *make_tree (char *struc)
+</pre><p> Constructs a <a class="el" href="structTree.html">Tree</a> ( essentially the postorder list ) of the structure 'struc', for use in <a class="el" href="treedist_8h.html#a3b21f1925f7071f46d93431a835217bb" title="Calculates the edit distance of the two trees.">tree_edit_distance()</a>. </p>
+<pre class="fragment">float tree_edit_distance (Tree *T1,
+ Tree *T2)
+</pre><p> Calculates the edit distance of the two trees. </p>
+<pre class="fragment">void free_tree(Tree *t)
+</pre><p> Free the memory allocated for <a class="el" href="structTree.html">Tree</a> t. </p>
+<dl class="section see"><dt>See also:</dt><dd><a class="el" href="dist__vars_8h.html" title="Global variables for Distance-Package.">dist_vars.h</a> and <a class="el" href="treedist_8h.html" title="Functions for Tree Edit Distances.">treedist.h</a> for prototypes and more detailed descriptions</dd></dl>
+<h3>Functions for String Alignment</h3>
+<pre class="fragment">swString *Make_swString (char *string)
+</pre><p> Convert a structure into a format suitable for <a class="el" href="stringdist_8h.html#a89e3c335ef17780576d7c0e713830db9" title="Calculate the string edit distance of T1 and T2.">string_edit_distance()</a>. </p>
+<pre class="fragment">float string_edit_distance (swString *T1,
+ swString *T2)
+</pre><p> Calculate the string edit distance of T1 and T2. </p>
+<dl class="section see"><dt>See also:</dt><dd><a class="el" href="dist__vars_8h.html" title="Global variables for Distance-Package.">dist_vars.h</a> and <a class="el" href="stringdist_8h.html" title="Functions for String Alignment.">stringdist.h</a> for prototypes and more detailed descriptions</dd></dl>
+<h3>Functions for Comparison of Base Pair Probabilities</h3>
+<p>For comparison of base pair probability matrices, the matrices are first condensed into probability profiles which are the compared by alignment.</p>
+<pre class="fragment">float *Make_bp_profile_bppm ( double *bppm,
+ int length)
+</pre><p> condense pair probability matrix into a vector containing probabilities for unpaired, upstream paired and downstream paired. </p>
+<pre class="fragment">float profile_edit_distance ( const float *T1,
+ const float *T2)
+</pre><p> Align the 2 probability profiles T1, T2<br/>
+. </p>
+<dl class="section see"><dt>See also:</dt><dd>ProfileDist.h for prototypes and more details of the above functions</dd></dl>
+<p><a class="el" href="mp_utils.html">Next Page: Utilities</a> </p>
+</div></div><!-- contents -->
+</div><!-- doc-content -->
+<!-- start footer part -->
+<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
+ <ul>
+ <li class="footer">Generated on Wed Jul 24 2013 13:38:59 for RNAlib-2.1.2 by
+ <a href="http://www.doxygen.org/index.html">
+ <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.1.1 </li>
+ </ul>
+</div>
+</body>
+</html>
git://source.jalview.org / jabaws.git / blobdiff