Answers.Body: <p>A <a href="https://en.wikipedia.org/wiki/Closed-form_expression" rel="noreferrer">closed-form</a> solution is offered in <em><a href="https://www.researchgate.net/profile/Alberto_Cabada/publication/5346653_An_Exact_Formula_for_the_Number_of_Alignments_Between_Two_DNA_Sequences/links/02bfe50efedf9c053e000000.pdf" rel="noreferrer">An exact formula for the number of alignments
  between two DNA sequences</a></em> by Torres, Cabada, and Nieto:</p>
  
  <p>$$f(m,n)=\sum_{k=0}^{min(m,n)}2^{k}\binom{m}{k}\binom{n}{k}$$</p>
  
  <p>If this solution seems reasonable, you could calculate this without BioPython, but with a simple <code>xrange</code> loop, the <a href="https://docs.python.org/2.0/ref/power.html" rel="noreferrer">power</a> operator, and <code>scipy.special.binom</code>:</p>
  
  <pre><code>#!/usr/bin/env python
  
  import sys
  import scipy.special
  
  def alignments(m, n):
      if m &lt; 0 or n &lt; 0:
          raise ValueError('m and n should be non-negative')
      s = 0
      b = min(m, n) + 1
      for k in xrange(0, b):
          s += (2 ** k) * scipy.special.binom(m, k) * scipy.special.binom(n, k)
      return s
  
  def main():
      m = 4
      n = 2
      a = alignments(m, n)
      assert (m == 4 and n == 2 and a == 41), "something went wrong!"
      sys.stdout.write("alignments(%d, %d) = %d\n" % (m, n, a))
  
  if __name__ == "__main__":
      main()
  </code></pre>
  
  <p>I don't know what your <code>m</code> and <code>n</code> are, but keep in mind that this solution grows quickly. Also, I did some digging and scipy <a href="https://stackoverflow.com/a/22966919">approximates</a> the calculation of the binomial coefficient, which is probably going to be an issue for large <code>m</code> and <code>n</code>. </p>
  
  <p>If you're working with large values, you may want to look into using the Python <code>long</code> type and consider the accuracy of the answer. The Stack Overflow link offers alternatives to scipy that generate an exact calculation of the binomial coefficient, at the cost of a longer runtime.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-23T18:21:03.197Z
Answers.LastActivityDate: 2017-10-24T18:37:58.030Z
Answers.LastEditDate: 2017-10-24T18:37:58.030Z
Answers.UserDisplayName: Alex Reynolds
Body: <p>I was looking BioPython to calculate the number of possible alignments between two sequences. Let's say there are two input sequences with the length of <em>m</em> and <em>n</em>. The program will count the possible number of alignments based on the length of two sequences. </p>
  
  <p>Is it possible to do that with BioPython? If not, how can I do that?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-23T16:43:27.160Z
Comments.Text: Which kind of sequences DNA, RNA or proteins? How have you tried to do so? What do you expect to learn from it?
Comments.UserDisplayName: llrs
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-23T16:53:43.103Z
Comments.Text: And the third question? Why do you need to know? (By the way, if you don't try why do you expect random people on the internet to help you?, Not that someone can't but it is harder to provide help if one doesn't see research effort)
Comments.UserDisplayName: llrs
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-23T17:58:28.450Z
Comments.Text: Seems like a homework assignment where they are asking for the theoretical number of alignments.  even down to the typical n and m nomenclature.
Comments.UserDisplayName: Bioathlete
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-10-24T11:05:00.653Z
Comments.Text: You should define what you mean by "possible alignment". Biopython will only help you use tools that chose among the possible alignments, based on certain criteria.
Comments.UserDisplayName: bli
Tags: <python><phylogenetics>
Title: Counting number of possible alignments between two DNA sequences using python
ThreadText: # Counting number of possible alignments between two DNA sequences using python
  
  (Asked by: username_0 on 2017-10-23)
  
  I was looking BioPython to calculate the number of possible alignments between two sequences. Let's say there are two input sequences with the length of *m* and *n*. The program will count the possible number of alignments based on the length of two sequences.
  
  Is it possible to do that with BioPython? If not, how can I do that?
  
  **Tags:** python, phylogenetics
  
  > **Comments:**
  > **username_1**: Which kind of sequences DNA, RNA or proteins? How have you tried to do so? What do you expect to learn from it?  
  > **username_1**: And the third question? Why do you need to know? (By the way, if you don't try why do you expect random people on the internet to help you?, Not that someone can't but it is harder to provide help if one doesn't see research effort)  
  > **username_2**: Seems like a homework assignment where they are asking for the theoretical number of alignments.  even down to the typical n and m nomenclature.  
  > **username_3**: You should define what you mean by "possible alignment". Biopython will only help you use tools that chose among the possible alignments, based on certain criteria.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2017-10-23. Score: 10 | Accepted answer
  
  A [closed-form](https://en.wikipedia.org/wiki/Closed-form_expression) solution is offered in *[An exact formula for the number of alignments
  between two DNA sequences](https://www.researchgate.net/profile/Alberto_Cabada/publication/5346653_An_Exact_Formula_for_the_Number_of_Alignments_Between_Two_DNA_Sequences/links/02bfe50efedf9c053e000000.pdf)* by Torres, Cabada, and Nieto:
  
  $$f(m,n)=\sum\_{k=0}^{min(m,n)}2^{k}\binom{m}{k}\binom{n}{k}$$
  
  If this solution seems reasonable, you could calculate this without BioPython, but with a simple `xrange` loop, the [power](https://docs.python.org/2.0/ref/power.html) operator, and `scipy.special.binom`:
  
  ```
  #!/usr/bin/env python
  
  import sys
  import scipy.special
  
  def alignments(m, n):
      if m < 0 or n < 0:
          raise ValueError('m and n should be non-negative')
      s = 0
      b = min(m, n) + 1
      for k in xrange(0, b):
          s += (2 ** k) * scipy.special.binom(m, k) * scipy.special.binom(n, k)
      return s
  
  def main():
      m = 4
      n = 2
      a = alignments(m, n)
      assert (m == 4 and n == 2 and a == 41), "something went wrong!"
      sys.stdout.write("alignments(%d, %d) = %d\n" % (m, n, a))
  
  if __name__ == "__main__":
      main()
  
  ```
  
  I don't know what your `m` and `n` are, but keep in mind that this solution grows quickly. Also, I did some digging and scipy [approximates](https://stackoverflow.com/a/22966919) the calculation of the binomial coefficient, which is probably going to be an issue for large `m` and `n`.
  
  If you're working with large values, you may want to look into using the Python `long` type and consider the accuracy of the answer. The Stack Overflow link offers alternatives to scipy that generate an exact calculation of the binomial coefficient, at the cost of a longer runtime.
  
  
  ---
  
  