<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hiruna Samarakoon on Medium]]></title>
        <description><![CDATA[Stories by Hiruna Samarakoon on Medium]]></description>
        <link>https://medium.com/@hiruna72?source=rss-508462c828e9------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*QlOrK3Enyo5Ei2rg.jpg</url>
            <title>Stories by Hiruna Samarakoon on Medium</title>
            <link>https://medium.com/@hiruna72?source=rss-508462c828e9------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 20:37:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@hiruna72/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[HMM for Gene Annotation]]></title>
            <link>https://medium.com/swlh/hmm-for-gene-annotation-aa10dd1c538d?source=rss-508462c828e9------2</link>
            <guid isPermaLink="false">https://medium.com/p/aa10dd1c538d</guid>
            <category><![CDATA[bioinformatics]]></category>
            <category><![CDATA[gene]]></category>
            <category><![CDATA[hmm]]></category>
            <category><![CDATA[viterbi]]></category>
            <category><![CDATA[hidden-markov-models]]></category>
            <dc:creator><![CDATA[Hiruna Samarakoon]]></dc:creator>
            <pubDate>Fri, 26 Jun 2020 08:43:56 GMT</pubDate>
            <atom:updated>2020-07-09T08:37:41.320Z</atom:updated>
            <cc:license>http://creativecommons.org/publicdomain/zero/1.0/</cc:license>
            <content:encoded><![CDATA[<h3>The problem and the solution</h3><p>What we see is DNA and cannot see underlying genes. Not all DNA corresponds to genes. Given a DNA sequence how to detect subsequences of DNA corresponding to genes?</p><p>We can use a Hidden Markov Model to determine the underlying proteins (or genes) given a DNA sequence as the input.</p><p>The rest of the article explains how this is done.</p><h3>Background — DNA, RNA and Genes</h3><p>The following is a DNA sequence.</p><pre>ACCTGCTACTCG</pre><p>We use the process called <em>Transcription</em> to convert DNA into RNA. The following is the corresponding RNA strand.</p><pre>UGGACGAUGAGC</pre><p>We did the following mapping in the transcription process</p><pre>A &gt; U, C &gt; G, G &gt; C, T &gt; A</pre><p>Once RNA is <em>pre-RNA</em> as it has both <em>Introns</em> and <em>Exons</em>. <em>Introns</em> do not code for proteins and hence should be removed. <em>Exons</em> should be spliced together to build <em>mature mRNA. Exons</em> do code for proteins. For more information about <em>introns</em> and <em>exons</em> please watch this <a href="https://www.youtube.com/watch?v=_asGjfCTLNE">video by Beverly Biology</a>.</p><p>A <em>Codon </em>is a DNA strand a length of 3 bases. Next we splice mature mRNA into codons. Let’s assume that the mature mRNA is the same as the original pre-RNA. Then we get 4 codons. Here let’s assume the sequence has no <em>introns</em>.</p><pre>UGG ACG AUG AGC</pre><p>We look up the genetic code table to reveal the corresponding gene.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/294/1*y8iVYspTFwv8Zs69OP5S-g.png" /><figcaption><strong>Fig 1</strong> — The genetic code with three-letter and single-letter amino acid designations, and color coding according to amino acid polarity. The three bases in a codon are matched against the chart in the order — leftmost column, header, and the rightmost column. (source-Bioinformatics for Evolutionary Biologists by Bernhard Haubold and Angelika Börsch-Haubold)</figcaption></figure><h3>Markov Property</h3><p>Consider predicting the next word of a sentence.</p><pre>The first day at ...</pre><p>Fundamentally we can propose two different models to predict the next word after “<em>at”. </em>The first model would only consider the current word — <em>“at” </em>to predict the next word. The second model would consider a set of previous words to predict the word, e.g., {<em>the, first, day, at}.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/654/1*-eRm6rtUuUfnBOnDVwTsDA.png" /><figcaption><strong>Fig 2</strong>— Probability of <strong>n+1</strong> state being <strong>j</strong> given a history of states, only depends on the current state <strong>n</strong> being <strong>i. </strong>Not to be confused with the total probability of <strong><em>n+1 </em></strong><em>state being </em><strong><em>j </em></strong><em>which is the sum of all such probabilities.</em></figcaption></figure><p>The first model is based on Markov Property, i.e., if the conditional probability distribution of future states of a stochastic process depends only upon the present state and not on the sequence of events that preceded it, the model adopts Markov Property.</p><p>note — in the above example the first model is not an ideal prediction model as it does not consider the previous states. However, some problems can be formulated with Markov property with greater confidence.</p><pre>e.g.:  determining the state of the next state (whether the base is a part of a gene or not) can be done without “memorizing” the states of the past bases, except for the current base. Since we have a finite number of states and it does not depend on the time when we transit from the current state to next, gene annotation problem comes under <strong>discrete time, discrete states Markov chain</strong>. Also determining the probability of the next state does not depend on how many states were evaluated before, hence we can classify this problem under <strong>time-homogeneous</strong> chains.</pre><h3>What is a HMM?</h3><p>HMM is an extension of the Markov Model (refer <a href="https://en.wikipedia.org/wiki/Markov_model">https://en.wikipedia.org/wiki/Markov_model</a>). In HMM we come across events and observations.</p><p>The event (or internal state) is not observable and can only be predicted by the observations and events are responsible for emitting observations.</p><p>If the number of internal states is N, the transition probabilities are described by a N x N matrix.</p><pre>the value in iᵗʰ row and jᵗʰ column gives the transition probability from iᵗʰ state to jᵗʰ state.</pre><p>If the number of observations is M, the emission probabilities are described by a N x M matrix.</p><pre>the value in iᵗʰ row and jᵗʰ column gives the probability of emitting jᵗʰ observation when the state is i.</pre><p>note — if the model was a completely deterministic model (no probability phenomenon) each event will only correspond to a particular observation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ECFulcfE3xKBgPdu92D8Mg.png" /><figcaption><strong>Fig 3</strong>— Notations used in HMM model src-<a href="https://scialert.net/fulltext/?doi=jas.2012.1518.1525">https://scialert.net/fulltext/?doi=jas.2012.1518.1525</a></figcaption></figure><p><em>L</em> represents the sequential structure of the input and in our case <em>k </em>is not time but represents the current DNA base we are at.</p><p>π is a N x 1 vector consisting of initial probabilities. For example if N =3 and π = [0.25 0.15 0.60] then there is a 1/4 chance of starting at state 1.</p><pre>From a biological point of view it is most likely to start from a DNA base that does not count to a gene thus, initial probability corresponding to that state will be much higher.</pre><h3>Example</h3><p>Consider a model with two internal states Coding (C) and Non-coding (N). A coding state represents <em>exons</em> and non-coding state represents the reset of the <em>codons</em>. We have four observations — A, C, T, and G. How can we fill in the matrices A and B? This is called the learning problem of HMM. In this example we only study the evaluation problem and the decoding problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/667/1*F684lNRFC3MBIaYtAFBqLw.png" /><figcaption><strong>Model 1</strong>— Coding and Non-coding are the two hidden states and the arrows mark transitions and their probabilities. Inside each state, the observations are described with their emission probabilities at a particular state src-<a href="https://scialert.net/fulltext/?doi=jas.2012.1518.1525">https://scialert.net/fulltext/?doi=jas.2012.1518.1525</a></figcaption></figure><pre>         C       N<br>A = C [0.995   0.005]<br>    N [0.010   0.99]</pre><pre>         A   T    C    G<br>B = C [0.3  0.3  0.2  0.2]<br>    N [0.1  0.1  0.4  0.4]</pre><h4>Evaluation problem</h4><p>This is used to evaluate the model. Given a DNA sequence (observations sequence), the probability of emitting a particular observation is calculated. Note that a hidden state is responsible for an observation. Because of the probability phenomenon an observation can be decoded to many hidden states. For example in the above matrix B, observing base T can be decoded to both states C and N. Decoding the best hidden state sequence is the decoding problem. It is necessary to consider all the possible hidden state sequences when calculating the probability of an observation. If a real-world observation yields an unsatisfactory probability the model is poor and should be improved by revisiting the learning problem and/or modifying the model.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/702/1*t_W1ynRotEwacsMoiqElCA.png" /><figcaption><strong>Fig 4</strong>— L is the observation sequence. S is an arbitrary internal state sequence.</figcaption></figure><pre>example : If π = [0.8 0.2], evaluating the above HMM for an observation sequence (TG) yields a probability of 5.6% approximately.</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*IMFRyHCwm-6z9bvrq3r72A.png" /><figcaption><strong>Fig 5</strong>—L is the observations sequence. C denotes the internal state “Coding” and N denotes the internal state “Non-coding”.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/982/1*RzeFXmn2N0Og8ep1ZOieng.png" /><figcaption><strong>Fig 6</strong>— Probability of observing the sequence TG if the internal state sequence is NC.</figcaption></figure><p>When the state space and the observation sequence gets larger the more compute-intensive the evaluation becomes, e.g., a model with 2 states has to consider 2³ hidden state sequences for a given sequence with 3 observations. Because of this forward algorithm and backward algorithms are used to evaluate the model efficiently.</p><h4>Decoding problem</h4><p>In this problem we find the most probable hidden state sequence that gives rise to a particular observation sequence. For example for a given DNA sequence the most probable C and NC states sequence is found. There are two variations in decoding problem,</p><ol><li>Find the sequence of internal states that has, as a whole, the highest probability (Viterby algorithm).</li><li>Find for each observation the internal state that has the highest probability (Posterior-decoding algorithm).</li></ol><p>Though the two problems seem the same, Viterby algorithm gives a “valid” hidden state sequence where Posterior decoding algorithm may give an invalid hidden state sequence. An invalid state sequence would have two consecutive states P and Q, but the transition matrix describes as there is a zero transition probability from P to Q.</p><h4>The notion of a stochastic process</h4><p>We can present the idea in decoding problem 1 mathematically,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/245/1*Zk-4RBGe6iWKD770uZXklQ.png" /><figcaption><strong>Fig 7</strong>— The joint probabilities — for a given observation sequence L possible hidden state sequence(s) S</figcaption></figure><p>We can treat S as a random variable. More precisely as a random vector that has a set of random variables. s₁,….sₙ and s’₁,….s’ₙ are two realizations. In either case, the definition of a stochastic process matches the presentation.</p><pre>— A random process or stochastic process is a family of random variables indexed by an ordered or index set denoted by T. The index set can be discrete or continuous and usually refers to time.—</pre><h4>Generative idea</h4><p>Starting from a particular state, if we keep transiting from state to state, <strong>Model 1 </strong>would generate varying lengths of coding and non-coding regions but they would have average lengths of 99.5 and 99 bases respectively. That is because there is a 99.5% chance of staying on a coding state and a 99% chance of staying on a non-coding state.</p><h4>Time dynamics</h4><p>Though the common usage of HMM in gene annotation is to reveal the underlying states given an observation sequence, we can use the matrix <strong>A</strong> to analyze its time dynamics to find the probability of nᵗʰ state being j, given the 0th state is i.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/1*CZnEClvuB9YIjcTPBAvgtQ.png" /><figcaption><strong>Fig 8</strong>— n-step transition probability</figcaption></figure><p>The matrix Aⁿ has entries for n-step transition probabilities.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/1*KFTPLHxS5Qy1M74apdMpwA.png" /><figcaption><strong>Fig 9</strong>— If P is a 2 x 2 transition matrix, Pⁿ can be calculated where λ2 = 1-p-q and p and q are transition probabilities</figcaption></figure><pre>In our example p = 0.005, q = 0.01 and λ2 = 0.94. When n→∞, that is when the state sequence grows infinitely, we will find state <em>C </em>and <em>NC </em>with 66.67% and 33.33% probabilities respectively.</pre><pre>Regardless of the initial state there is a 16.67% chance of landing on state <em>C </em>and an 83.33% chance of landing on state <em>NC. </em>Therefore, this is a <strong>limit distribution</strong>.</pre><h4>Classification of states</h4><p>The following are two classifications,</p><ol><li>Recurrent and transient states (classes)</li><li>Periodic and aperiodic states (classes)</li></ol><p>For more information about the classification of states refer <a href="https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php">https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php</a></p><pre>In the above state machine, state <em>C</em> can be accessed from state <em>NC</em> and vice versa. Hence state <em>C</em> and <em>NC</em> are communicating with each other,i.e., both the states are in the same communicating class and it is the only class. Therefore the state machine is <strong>irreducible</strong> and the class is a <strong>recurrent class</strong> (in a finite Markov chain there is at least one recurrent class). Since the states in a recurrent class are also recurrent, here both the states are recurrent, i.e., the total number of visits to a state over time is infinite.</pre><pre>The state machine has <strong>zero absorbing states</strong> (an absorbing state&#39;s leaving transition probabilities are zero). </pre><pre>The <strong>aperiodicity</strong> of the above state machine can be deduced from three different logic,</pre><pre>1. The two states have self-transitions (periodicity is 1). 1 is co-prime to every integer and thus the states are aperiodic. Thus the chain is aperiodic.</pre><pre>2. The state machine is irreducible. At least one state has a self-transition. Thus the chain is aperiodic.</pre><pre>3. The chain is aperiodic if and only if there exists a positive integer <em>n</em> such that all elements of the matrix Aⁿ are strictly positive. A has strictly positive elements. Thus the chain is aperiodic.</pre><h4>Stationary distributions</h4><p>Initial distribution π = [<em>π₁,π₂,π₃,</em>…,<em>π</em>ₖ,…] is a stationary distribution if πA = π. Then π<em>ᵢ</em> describes what proportion of time that is spent in state <em>i</em> in the long run. A model may not have a stationary distribution or maybe more than one. For an irreducible Markov chain has a stationary distribution it is unique. If the state space is finite and the chain is irreducible, then a unique stationary distribution exists.</p><pre>In our case, let π = [<em>π₁,π₂</em>]. Then πA = π gives,</pre><pre>   0.995<em>π₁ + 0.01π₂ = π₁<br>   0.005π₁ + 0.99π₂ = π₂</em></pre><pre>Solving these with <em>π₁+π₂ = 1 gives π₁ = 2/3 and π₂ = 1/3.</em></pre><pre>Hence, the chain <strong>has a stationary distribution</strong> and since the chain is irreducible it is unique.</pre><h3>A more refined HMM for gene annotation</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*CWARryVaCWYksLWufJYaHA.png" /><figcaption><strong>Fig 1 0</strong>— An ORF is a continuous stretch of codons that begins with a start codon and ends at a stop codon.</figcaption></figure><p>In this scenario we are interested in finding four hidden states —start codon, ORF, stop codon, and the non-coding region. With a similar argument as mentioned earlier we can use Markov property to model this problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/477/1*dlOGoYtvuwuNewPvBGqArg.png" /><figcaption><strong>Model 2</strong> — A codon is a sub-string of 3 bases. Hence Start codon and Stop codon states emit 3 bases in contrast to the first example where each state emitted a single base. Non-State emits 1 base and has a self-transition to make sure the model supports arbitrary lengths between genes (instead of emitting 3 bases). ORF (Codon state) is a multiplication of 3 thus, emits 3 bases. Self-transition in the Codon state ensures varying lengths of ORFs. Based on the current state we are in, the length of the observed sub-sequence vary, e.g., if we are in Non state we only consider 1 base as the observation at that state. In the same manner, the emission probability space expands to include emission probabilities for groups of 3 bases. The transition probability values were chosen arbitrarily.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/781/1*5_09o7VlZkJW89iv5jKSgw.png" /><figcaption><strong>Fig 1 1</strong>— The portion of the DNA bases in orange represents the reverse strand. When genes on the reverse strand are considered, technically the stop codons are met before ORFs.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/649/1*MsUuWqdJVBdoQRDxxaw5ug.png" /><figcaption><strong>Model 3</strong>— Now that we consider the reverse strand two new states are introduced. The reason we cannot have a transition from the original Stop state to Codon state is biologically the Stop⁺ state and Stop⁻ states are different. They emit codons with different emission probabilities. The same argument is valid for having Start⁺ and Start⁻ states</figcaption></figure><pre>In both above Markov processes all the states communicate with each other. Thus the Markov chain is <strong>irreducible</strong> and there exists one equivalence class.</pre><pre>The state machine has <strong>zero absorbing states</strong>.</pre><pre>Two states have self-transitions. Hence the states are recurrent - the class is <strong>recurrent</strong>.</pre><pre>Using the same argument we can deduce that the chain is <strong>aperiodic</strong>.</pre><p>Let’s assume the <strong>Model 2 </strong>has the following transition matrix A,</p><pre>           Codon    Stop    Start    Non<br>A = Codon [0.99     0.01     0        0]<br>    Stop  [0        0        0        1]<br>    Start [1        0        0        0] <br>    Non   [0        0        0.05  0.95]</pre><p>Then we can try to find a stationary distribution s.t πA = π for π = [<em>π₁,π₂,π₃,π₄</em>]</p><pre>0.99<em>π₁ + π₃ = π₁<br></em>0.<em>01π₁      = π₂<br></em>0.<em>05π₄      = π₃<br>π₂ + 0.95π₄ = π₃</em></pre><pre><em>gives π₂/π₁ = 0.01, π₃/π₄ = 0.05</em></pre><pre>Solving these with <em>π₁+π+π₃+π₄ = 1 gives,<br>π₁=1/1.22, π₂=1/122, π₃=1/122 and π₄=10/61.</em></pre><pre>Hence, the chain <strong>has a stationary distribution</strong> and since the chain is irreducible it is unique.</pre><h3>HMMs in bioinformatics</h3><p>The same HMM presented in <strong>Model 1</strong> can be used to detect CpG islands in a DNA sequence with little modifications. Simply a CpG island is a region that has a relatively high density of C and G bases. We can argue that the current state is enough to predict the next state in this problem as well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/1*BzjGSPgsQm0O6rMe7_9wZw.png" /><figcaption><strong>Model 4</strong> — CpG and Non-CpG are the two hidden states and the arrows mark transitions and their probabilities. Inside each state the observations are described with their emission probabilities at a particular state src-<a href="https://www.youtube.com/watch?v=d5NMrA2HkG4">https://scialert.net/fulltext/?doi=jas.2012.1518.1525</a> Note the emission probabilities of the bases C and G are higher in the CpG state and lower in the Non-CpG state. Thus the model holds the underlying biological aspect.</figcaption></figure><p>If we consider the generative idea for <strong>Model 4 </strong>the generator would produce arbitrary lengths of CpG regions but on average they will be 999 bases (≈1kb) long. Non-CpG regions will be 99999 bases (≈100kb) long on average.</p><h3>Viterby algorithm</h3><p>Recall that we can use Viterby algorithm to determine the best possible still valid hidden state sequence for a given observation sequence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/1*IYWtZlZVeBa2SFuN5EbZ8Q.png" /><figcaption><strong>Fig 12</strong>—Finding the probability of a hidden sequence S given the observation sequence L can be expressed as the joint probability and then using Baye’s rule transformed into three calculatable components. The denominator is the evaluation problem and remains constant during the process of finding the optimal S.</figcaption></figure><p>Let’s define Rᵢˢ as the optimal hidden state sequence up to iᵗʰ observation that has the hidden state <em>s </em>as the iᵗʰ state.</p><p>example : Find the optimal hidden state sequence S’ for the observation sequence L = [ACT]. Denote Non-CpG state by <em>N</em> and CpG state by <em>I</em>. The initial probabilities are [0.99 0.01] for <em>N</em> and <em>I</em> respectively. The initial probability makes sense as it is highly likely to start at a Non-CpG region.</p><p>Here, we have to calculate R₀<em>ᴺ</em>, R₀<em>ᴵ</em>, R₁<em>ᴺ</em>, R₁<em>ᴵ</em>, R₂<em>ᴺ</em>, R₂<em>ᴵ</em>, R₃<em>ᴺ</em>, and R₃<em>ᴵ</em>. Each Rᵢˢ has to choose the best from the previous Rᵢ₋₁. For example R₁<em>ᴺ</em> has to choose between R₀<em>ᴺ</em> x Prob. of transiting from state <em>N</em> to <em>N</em> x Prob. of emitting base A at state <em>N</em> Vs R₀ᴵ x P(<em>I</em> | <em>N</em>) x P(A | <em>N</em>). In a more compact form,</p><pre>R₁<em>ᴺ</em> = max(R₀<em>ᴺ</em> x P(<em>N</em> <em>|</em> <em>N</em>) x P(&#39;A&#39; | <em>N</em>), R₀<em>ᴵ</em> x P(<em>N</em> | <em>I</em>) x P(&#39;A&#39; | <em>N</em>))<br>R₀<em>ᴺ = 0.99 and </em>R₀<em>ᴵ = 0.01 (initial probabilities)</em></pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QfFpuE2OzQ6Wx_ck3YE9Xg.png" /><figcaption><strong>Fig 1 3</strong> — Two hidden states N<em> and </em>I; ACT observation sequence. We compare <em>Y</em>₁ and <em>Y</em>₂<em> to find max and backtrack to find the optimal hidden state sequence. Generally, the backtracking path could be the green arrows, blue arrows, or a different path. In this case Y</em>₁ is larger and green arrows build the backtracking path. Hence, the optimal hidden state sequence is NNN.</figcaption></figure><h3>Why Viterbi algorithm works?</h3><p>As shown in Fig 13 the algorithm yields <em>NNN</em>… or <em>III</em>…as the hidden state sequence most of the time. It depends on the initial probability. If the initial probability of being in the state <em>I</em> is higher then we will get <em>III…</em></p><p>However, we are interested in a mix of <em>N</em> and <em>I</em> in the hidden state sequence. To yield such a sequence we understand that there should be a moment like Rᵢ₋₁<em>ᴺ</em> x P(<em>N</em> <em>|</em> <em>N</em>) x P(Eᵢ | <em>N</em>) &lt; Rᵢ₋₁<em>ᴵ</em> x P(<em>N</em> | <em>I</em>) x P(Eᵢ | <em>N</em>) where <em>I</em>→<em>N </em>is favored over <em>N</em>→<em>N, </em>or a moment like Rᵢ₋₁<em>ᴵ </em>x P(<em>I</em> <em>|</em> <em>I</em>) x P(Eᵢ | <em>I</em>) &lt; Rᵢ₋₁<em>ᴺ</em> x P(<em>I</em> | <em>N</em>) x P(Eᵢ | <em>I</em>) where <em>N</em>→<em>I </em>is favored over <em>I</em>→<em>I.</em></p><p>There is a huge penalty involved with <em>I</em>→<em>N </em>compared to <em>N</em>→<em>N </em>(≈x10³ times costly to jump from <em>I</em>→<em>N </em>than from<em> N</em>→<em>N</em> )<em>. </em>Similarly, it is ≈10⁵ times costly to jump from <em>N</em>→<em>I </em>than from<em> I</em>→<em>I. </em>But what is fascinating is Viertby works and this kind of jumps occur at the correct moment.</p><p>Though it seems impossible the emission probabilities play the role of compensating.</p><pre>For example consider P(‘G’|I) = 0.3 and P(‘G’|N) = 0.2. </pre><pre>P(‘G’|I)/P(‘G’|N)  = 1.5</pre><pre>Powers of 1.5<br>     n =  20    40    60     80<br>(1.5)ⁿ = 3x10³ 1x10⁷ 3x10¹⁰ 1x10¹⁴</pre><pre>Let&#39;s say the initial probability of starting at <em>N </em>is higher. When the observation sequence has a part like ...A₆₀GCCCG... there is a moment where Rᵢ₋₁<em>ᴵ </em>x P(<em>I|I</em>) x P(Eᵢ|<em>I</em>) &lt; Rᵢ₋₁<em>ᴺ</em> x P(<em>I</em>|<em>N</em>) x P(Eᵢ|<em>I</em>). And at that moment <em>N</em>→<em>I </em>occurs. It is in intuitively correct as we expect more Gs in a CpG state.</pre><pre><strong>note 1</strong> - 99.999/99.9≈1 hence, we can ignore P(<em>N</em>|<em>N</em>) and P(<em>I</em>|<em>I</em>).</pre><pre><strong>note 2</strong> - a cross jump does not only have to pay the penalty of the cross jump itself but also the penalty of the ratio difference between the initial probabilities, e.g.,<em>I</em>→<em>N transition has to compensate for the initial probability ratio difference </em>0.99/0.01 too.</pre><p>For more information on this watch <a href="https://youtu.be/d5NMrA2HkG4?t=4079">https://youtu.be/d5NMrA2HkG4?t=4079</a></p><p>The run time for a k-state HMM on a sequence of length L when all states are connected to each other is O(k²L).</p><h3>References</h3><ol><li>Gene Finding Using Hidden Markov Model — Mini Review <a href="https://scialert.net/fulltext/?doi=jas.2012.1518.1525">https://scialert.net/fulltext/?doi=jas.2012.1518.1525</a></li><li>Classification of States <a href="https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php#example11_6">https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php#example11_6</a></li><li><a href="https://en.wikipedia.org/wiki/Markov_property">https://en.wikipedia.org/wiki/Markov_property</a></li><li>Introns vs Exons <a href="https://www.youtube.com/watch?v=_asGjfCTLNE">https://www.youtube.com/watch?v=_asGjfCTLNE</a></li><li>Bioinformatics for Evolutionary Biologists by Bernhard Haubold and Angelika Börsch-Haubold</li><li>Markov and Hidden Markov Models of Genomic and Protein Features <a href="https://www.youtube.com/watch?v=d5NMrA2HkG4">https://www.youtube.com/watch?v=d5NMrA2HkG4</a></li><li>Events and Random Variables <a href="http://www.randomservices.org/random/prob/Events.html">http://www.randomservices.org/random/prob/Events.html</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aa10dd1c538d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/hmm-for-gene-annotation-aa10dd1c538d">HMM for Gene Annotation</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Compiling HDF5 on Android with multi-threading support]]></title>
            <link>https://medium.com/@hiruna72/compiling-hdf5-on-android-with-multi-threading-support-82658b1c0141?source=rss-508462c828e9------2</link>
            <guid isPermaLink="false">https://medium.com/p/82658b1c0141</guid>
            <category><![CDATA[android-app-development]]></category>
            <category><![CDATA[hdf5]]></category>
            <category><![CDATA[termux]]></category>
            <category><![CDATA[arm]]></category>
            <category><![CDATA[cross-compile]]></category>
            <dc:creator><![CDATA[Hiruna Samarakoon]]></dc:creator>
            <pubDate>Sun, 07 Jun 2020 08:25:31 GMT</pubDate>
            <atom:updated>2020-06-07T08:41:46.557Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/784/1*2flQZ-WpA9b1f_kLRimRBQ.png" /></figure><p>I once wanted to create a shared library of the popular bioinformatics tool — <a href="https://github.com/jts/nanopolish">Nanopolish</a>. Nanopolish uses two third-party libraries —<a href="https://github.com/samtools/htslib/"> htslib</a> and <a href="https://bitbucket.hdfgroup.org/projects/HDFFV/repos/hdf5/browse">hdf5</a>. My idea was to cross-compile Nanopolish on my laptop (architecture — X86) and get a shared library instance for armeabi-v7a architecture using the Android toolchain. However, this was not possible because the source code of hdf5 could not be cross-compiled. The reason for this, as I understood was, in the compilation process of hdf5, it executes a program to generate a header file, which contains underlying hardware configuration details. The execution of this program fails if the target architecture is not as same as the compiler architecture. HDF5 group also has suggested to not to cross-compile hdf5 <a href="https://portal.hdfgroup.org/pages/viewpage.action?pageId=48808266">(https://portal.hdfgroup.org/pages/viewpage.action?pageId=48808266</a>).</p><p>Given the limitations above, to create an armeabi-v7a instance of hdf5, one can use either a computer with the architecture armeabi-v7a or use a mobile phone which has armeabi-v7a. To check if your mobile device has armeabi-v7a, download <a href="https://play.google.com/store/apps/details?id=com.inkwired.droidinfo&amp;hl=en">Droid Hardware Info</a> from Google play store and check for “instruction set” (see image). If your architecture is not armeabi-v7a but something else (most probably arm64-v8a) you can still go ahead with compiling to produce a dynamic library for the respective architecture. I decided to compile hdf5 on an Android device itself. I used <a href="https://play.google.com/store/apps/details?id=com.termux&amp;hl=en">termux </a>— a linux like terminal for Android.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/317/1*yupEZa-C5ftu5xRAcfa9zA.png" /><figcaption><strong>Instruction Sets </strong>row includes the supported architecture(s)</figcaption></figure><h4>HDF5 without multi-threading support</h4><p>Instead of cloning from the source code of hdf5, I used a released version of hdf5. Download it to termux using wget.</p><pre>wget <a href="https://support.hdfgroup.org/ftp/HDF5/releases/hdf5-1.10/hdf5-1.10.4/src/hdf5-1.10.4.tar.gz">https://support.hdfgroup.org/ftp/HDF5/releases/hdf5-1.10/hdf5-1.10.4/src/hdf5-1.10.4.tar.gz</a></pre><pre>tar -xzf hdf5-1.10.4.tar.gz</pre><pre>cp -r hdf5-1.10.4 hdf5-single-thread</pre><pre>cd hdf5-single-thread</pre><p>Run the following commands to get hdf5 libraries without multi-threading support.</p><pre>./configure CFLAGS=-fPIE LDFLAGS=-pie --with-pic --prefix=$install_dir </pre><pre>make -j 2</pre><pre>make install</pre><p>Now you should be able to find the compiled hdf5 libraries inside the folder specified in the configuration step.</p><h4>HDF5 with multi-threading support</h4><p>Hdf5 is much faster with multi-threading enabled. However, termux does not have the C source files for a set of C functions necessary to compile for multi-threading (this is actually an issue with Clang compiler for armeabi).</p><pre>cp -r hdf5-1.10.4 hdf5-multi-thread</pre><pre>cd hdf5-multi-thread</pre><pre>./configure CFLAGS=-fPIE LDFLAGS=-pie --with-pic --prefix=$PWD/libraries --enable-threadsafe --disable-hl</pre><pre>make -j 2</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rvHk60iJlmJ5CMZ1sEXuZA.png" /><figcaption>The compiler reports the error about the use of undeclared identifier ‘PTHREAD_CANCEL_DISABLE’</figcaption></figure><p>How can we resolve this? Well, I found an implementation of those particular C implementations <a href="https://github.com/tux-mind/libbthread">here</a>. I copied them all into a single file and the file was included as a header file (not the best way to do this, but it is a quick hack!). Do the following steps.</p><p>Copy <a href="https://github.com/hiruna72/libbthread/blob/master/cancelthread.h">https://github.com/hiruna72/libbthread/blob/master/cancelthread.h</a> file into hdf5-multi-thread/src folder.</p><p>Edit hdf5-multi-thread/src/H5TS.c source file to include <em>cancelthread.h </em>header file as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/611/1*j8bK9_5X2GTfmuaQzxuQ1A.png" /><figcaption>Include <strong>cancelthread.h</strong> header file in H5TS.c file</figcaption></figure><p>Continue compiling,</p><pre>make -j 2</pre><pre>make install</pre><p>Now you should find static and dynamic libhdf5 libraries inside the folder specified in the configuration step.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/453/1*WWXYMbq34UKvISa1PaJOKA.png" /><figcaption>Static and dynamic hdf5 libraries</figcaption></figure><p><strong>References</strong></p><p><a href="https://gitlab.com/arm-hpc/packages/-/wikis/packages/hdf5#build-details-for-version-1105-with-Arm-Compiler-for-HPC-200">https://gitlab.com/arm-hpc/packages/-/wikis/packages/hdf5#build-details-for-version-1105-with-Arm-Compiler-for-HPC-200</a></p><p><strong>PS</strong> — I sshed to termux from my laptop to make it easy to type and edit files. I have included basic steps to set it up (credits <a href="https://medium.com/@sanojpunchihewa">https://medium.com/@sanojpunchihewa</a>).</p><h4>How to access termux using a USB connection to a laptop</h4><ul><li>Make sure you have termux on your phone and <a href="https://www.xda-developers.com/install-adb-windows-macos-linux/"><em>adb</em></a> installed on your laptop. Turn on Developer options in your phone.</li><li>Set a password for termux (<a href="https://wiki.termux.com/wiki/Remote_Access#OpenSSH">https://wiki.termux.comwiki/Remote_Access#OpenSSH</a> )</li></ul><pre>$ passwd</pre><ul><li>Install openssh in termux</li></ul><pre>$ pkg install openssh</pre><ul><li>Run the daemon in termux</li></ul><pre>$ sshd</pre><ul><li>Run following on laptop to forward the laptop’s port number 8022 to the phone’s 8022 port</li></ul><pre>adb forward tcp:8022 tcp:8022</pre><ul><li>Connect the phone to the laptop using a USB cable.</li><li>Now use putty or ssh on your laptop to connect to termux.</li></ul><pre>ssh localhost -p 8022</pre><p><strong>Note</strong> by default, termux stores the $HOME folder into termux’s private storage. Run the following command to use any external directory. This creates a directory on your $HOME directory with the name <em>storage</em> which is the root of your device’s external directory.</p><pre>$ termux-setup-storage</pre><p>For more information refer <a href="https://pedronveloso.com/proper-git-client-android/">https://pedronveloso.com/proper-git-client-android/</a>.</p><p><em>Did you find this article useful? Please </em>👏<em> this post and share it!</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=82658b1c0141" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>