Answers.Body: <p>Here's a Cython approach that might suggest a generic approach to speeding up Python work. </p>
  
  <p>If you're manipulating (ASCII) character strings and performance is a design consideration, then C or Perl are probably preferred options to Python. </p>
  
  <p>In any case, this Cython test uses Python 3.6.3:</p>
  
  <pre><code>$ python --version
  Python 3.6.3 :: Anaconda custom (64-bit)
  </code></pre>
  
  <p>To install Cython, e.g.:</p>
  
  <pre><code>$ conda install -c anaconda cython
  </code></pre>
  
  <p>The Cython code below seems to offer about the same speed bump as the translation table — perhaps similar code is run under the hood of that.</p>
  
  <p>Two files are needed, starting with <code>setup.py</code>:</p>
  
  <pre><code>from distutils.core import setup
  from Cython.Build import cythonize
  
  setup(
    name = 'Reverse complement C test',
    ext_modules = cythonize("revcomp_c.pyx"),
  )
  </code></pre>
  
  <p>And then a second file called <code>revcomp_c.pyx</code>:</p>
  
  <pre><code>from libc.stdlib cimport malloc
  
  cdef int seq_len = 17
  cdef char *seq_dest = &lt;char *&gt;malloc(seq_len + 1)
  seq_dest[seq_len] = '\0'
  
  def reverse_complement_c_v1(str seq):
      cdef bytes py_bytes = seq.encode('ascii')
      cdef char *seq_src = py_bytes
      cdef int i = 0
      cdef int d = 0
      for i in range(seq_len):
          d = seq_len - i - 1
          if seq_src[i] == 'A':
              seq_dest[d] = 'T'
          elif seq_src[i] == 'G':
              seq_dest[d] = 'C'
          elif seq_src[i] == 'C':
              seq_dest[d] = 'G'
          elif seq_src[i] == 'T':
              seq_dest[d] = 'A'
      return seq_dest[:seq_len].decode('ascii')
  </code></pre>
  
  <p>This can be compiled into a Python module like so:</p>
  
  <pre><code>$ python setup.py build_ext --inplace
  </code></pre>
  
  <p>Then we can modify the test bench to include this Cython module and the relevant test method:</p>
  
  <pre><code>#!/usr/bin/env python
  import random
  import timeit
  from revcomp_c import reverse_complement_c_v1
  
  global complement
  complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
  
  DNAlength = 17
  
  #randomly generate 100k bases
  int_to_basemap = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
  num_strings = 500000
  random.seed(90210)
  DNAstrings = ["".join([int_to_basemap[random.randint(1,4)] for i in range(DNAlength)])
                for j in range(num_strings)]
  #get an idea of what the DNAstrings look like
  print(DNAstrings[0:5])
  
  def reverse_complement_naive(seq):
      this_complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
      return "".join(this_complement.get(base, base) for base in reversed(seq))
  
  def reverse_complement(seq):
      return "".join(complement.get(base, base) for base in reversed(seq))
  
  tic=timeit.default_timer()
  rcs = [reverse_complement_naive(seq) for seq in DNAstrings]
  toc=timeit.default_timer()
  baseline = toc - tic
  namefunc = {"naive implementation": reverse_complement_naive,
              "global dict implementation": reverse_complement,
              "Cython implementation (v1)": reverse_complement_c_v1}
  
  for function_name in namefunc:
      func = namefunc[function_name]
      tic=timeit.default_timer()
      rcs = [func(seq) for seq in DNAstrings]
      toc=timeit.default_timer()
      walltime = toc-tic
      print("""{}
         {:.5f}s total,
         {:.1f} strings per second
         {:.1f}% increase over baseline""".format(
             function_name,
             walltime,
             num_strings/walltime,
             100- ((walltime/baseline)*100)   ))
  </code></pre>
  
  <p>A sample run:</p>
  
  <pre><code>$ python ./revcomp_test.py
  ['ACTGCAATAGACCACGC', 'CAGCTTGAGCCATTAAC', 'GGCCCAAGAGTTCGAAC', 'CGACTGTCTCGAATTGT', 'ATCCGCTATGCGCCGTC']
  naive implementation
         1.73295s total,
         288525.0 strings per second
         -2.5% increase over baseline
  global dict implementation
         1.70896s total,
         292575.5 strings per second
         -1.0% increase over baseline
  Cython implementation (v1)
         0.21458s total,
         2330158.7 strings per second
         87.3% increase over baseline
  </code></pre>
  
  <p>One easy way to speed this up is to use a <code>static const unsigned char</code> array as an ASCII lookup table, which maps a residue directly to its complement. This would replace the nest of <code>if</code> statements and probably give a nice little boost (<a href="https://bioinformatics.stackexchange.com/a/3595/776">and it appears it does, making it among the best performers so far!</a>).</p>
  
  <p>Here is my fast implementation of a reverse complement function in C:</p>
  
  <p><a href="https://gist.github.com/alexpreynolds/4f75cab4350e9d937f4a" rel="noreferrer">https://gist.github.com/alexpreynolds/4f75cab4350e9d937f4a</a></p>
  
  <p>You might be able to use this directly in Python via the <code>subprocess</code> library. Outsourcing the reverse complement step to a utility written in C will almost always beat the best that Python can do, and you can do nice and important things like bounds checking etc. without losing much speed.</p>
  
  <p>It's unclear how "pure" the answer needs to be, but making a system call from Python seems fair if you're processing strings and your goal is performance.</p>
  
  <p>Another direction to take may be to look at multithreading, if you don't need ordered output. If you have many thousands of sequences stored in memory, you could split an array of sequences up into smaller arrays by use of offsets or array indices. Each thread would work on "rc"-ing sequences in its own piece of the array.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:16:15.373Z
Answers.Text: Nice, +1 for Cython
Answers.UserDisplayName: Chris_Rands
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:16:49.883Z
Answers.Text: Nice! Can you compare this to the `.translate()` version in my code? It'd be interesting to see how much Cython is able to speed things up in comparison given the general python overhead.
Answers.UserDisplayName: Devon Ryan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-22T00:51:12.120Z
Answers.Text: @Devon_Ryan: With this test bench, the "Cython implementation (v2)" on my Python 3 setup gave a 91.1% increase over baseline and "table" (translate) gave a 84.6% increase. I'm not sure how a Python 2 Cython setup compares.
Answers.UserDisplayName: Alex Reynolds
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:07:46.673Z
Answers.LastActivityDate: 2018-02-20T22:55:02.400Z
Answers.LastEditDate: 2018-02-20T22:55:02.400Z
Answers.UserDisplayName: Alex Reynolds
Answers.Body: <p>Another python extension but without cython. The source code is available at the bottom of this answer or <a href="https://gist.github.com/attractivechaos/15a61b2517c253bb31bffcde3e45c6e8" rel="noreferrer">from this gist</a>. On Mac with Python3:</p>
  
  <pre><code>string
     0.38166s total,
     1310067.4 strings per second
     84.4% increase over baseline
  seqpy
     0.20524s total,
     2436182.7 strings per second
     91.6% increase over baseline
  </code></pre>
  
  <p>On Linux with Python2 (seqpy is the first):</p>
  
  <pre><code>seqpy  
     0.10960s total,
     4561842.5 strings per second
     93.3% increase over baseline
  string 
     0.17811s total,
     2807330.9 strings per second
     89.1% increase over baseline
  </code></pre>
  
  <hr>
  
  <p>This is file <code>setup.py</code>:</p>
  
  <pre class="lang-python prettyprint-override"><code>from setuptools import setup, Extension
  
  seqpy_module = Extension('seqpy', sources = ["seqpy.c"])
  
  setup(
      name = "seqpy",
      description = "seqpy",
      ext_modules = [seqpy_module])
  </code></pre>
  
  <p>This is file <code>seqpy.c</code>:</p>
  
  <pre class="lang-c prettyprint-override"><code>#include &lt;stdlib.h&gt;
  #include &lt;stdint.h&gt;
  #include &lt;Python.h&gt;
  
  static unsigned char seq_comp_table[256] = {
        0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
       16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
       32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
       48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
       64, 'T', 'V', 'G', 'H', 'E', 'F', 'C', 'D', 'I', 'J', 'M', 'L', 'K', 'N', 'O',
      'P', 'Q', 'Y', 'S', 'A', 'A', 'B', 'W', 'X', 'R', 'Z',  91,  92,  93,  94,  95,
       64, 't', 'v', 'g', 'h', 'e', 'f', 'c', 'd', 'i', 'j', 'm', 'l', 'k', 'n', 'o',
      'p', 'q', 'y', 's', 'a', 'a', 'b', 'w', 'x', 'r', 'z', 123, 124, 125, 126, 127,
      128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
      144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
      160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
      176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
      192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
      208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
      224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
      240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
  };
  
  static PyObject *seqpy_revcomp(PyObject *self, PyObject *args)
  {
      PyObject *r;
      char *seq, *rev;
      int i, len;
      PyArg_ParseTuple(args, "s#", &amp;seq, &amp;len);
      rev = (char*)malloc(len);
      for (i = 0; i &lt; len; ++i)
          rev[len - i - 1] = seq_comp_table[(uint8_t)seq[i]];
      r = Py_BuildValue("s#", rev, len);
      free(rev);
      return r;
  }
  
  static PyMethodDef seqpy_methods[] = {
      {"revcomp", seqpy_revcomp, METH_VARARGS, "Reverse complement a DNA sequence"},
      {NULL, NULL, 0, NULL}
  };
  
  #if PY_MAJOR_VERSION &gt;= 3
  static struct PyModuleDef seqpy_module = { PyModuleDef_HEAD_INIT, "seqpy", NULL, -1, seqpy_methods };
  PyMODINIT_FUNC PyInit_seqpy(void) { return PyModule_Create(&amp;seqpy_module); }
  #else
  PyMODINIT_FUNC initseqpy(void) { Py_InitModule3("seqpy", seqpy_methods, NULL); }
  #endif
  </code></pre>
  
  <p>To compile and test:</p>
  
  <pre><code>python setup.py build_ext -i
  python -c 'import seqpy; print(seqpy.revcomp("GGGTT"))'
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T17:51:22.480Z
Answers.LastActivityDate: 2018-02-20T17:59:43.647Z
Answers.LastEditDate: 2018-02-20T17:59:43.647Z
Answers.UserDisplayName: user172818
Answers.Body: <p>Here is a revision of <a href="https://bioinformatics.stackexchange.com/a/3587/776">my original Cython answer</a> which incorporates my suggestion to use a <code>char</code> lookup array:</p>
  
  <pre><code>from libc.stdlib cimport malloc
  
  cdef int seq_len = 17
  cdef char *seq_dest = &lt;char *&gt;malloc(seq_len + 1)
  seq_dest[seq_len] = '\0'
  
  cdef char *basemap = [ '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',   '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  'T', '\0',  'G', '\0', '\0', '\0',  'C', '\0', '\0', '\0', '\0', '\0', '\0',  'N', '\0', '\0', '\0', '\0', '\0',  'A',  'A', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  't', '\0',  'g', '\0', '\0', '\0',  'c', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  'a',  'a' ]
  
  def reverse_complement_c_v2(str seq):
      cdef bytes py_bytes = seq.encode('UTF-8')
      cdef char *seq_src = py_bytes
      cdef int i = 0
      for i in range(seq_len):
          seq_dest[seq_len - i - 1] = basemap[&lt;int&gt;seq_src[i]]
      return seq_dest[:seq_len].decode('UTF-8')
  </code></pre>
  
  <p>In testing under OS X, Python 3.6.3:</p>
  
  <pre><code>$ python ./revcomp.py
  ['ACTGCAATAGACCACGC', 'CAGCTTGAGCCATTAAC', 'GGCCCAAGAGTTCGAAC', 'CGACTGTCTCGAATTGT', 'ATCCGCTATGCGCCGTC']
  ...
  Cython implementation (v1)
         0.20664s total,
         2419626.4 strings per second
         88.3% increase over baseline
  Cython implementation (v2)
         0.14170s total,
         3528668.5 strings per second
         92.0% increase over baseline
  </code></pre>
  
  <p>Using my lookup array approach ("v2") adds a very decent performance bump over using <code>if</code> blocks ("v1"), and you can keep everything as a Python string.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T18:55:16.333Z
Answers.LastActivityDate: 2018-02-20T19:16:22.180Z
Answers.LastEditDate: 2018-02-20T19:16:22.180Z
Answers.UserDisplayName: Alex Reynolds
Answers.Body: <p><strong>Use a <code>bytearray</code> instead of a <code>string</code> and then employ <code>maketrans</code> to translate</strong></p>
  
  <p>You do not need the more advanced string encoding capabilities of <code>string</code> to store a string of bases, but you're still paying for it in performance. Devon Ryan's suggestion of <code>maketrans</code> is the huge improvement, 10x faster than your naive implementation. Using the same approach, but swapping everything out for <code>byte</code>s allows a further 40% speed improvement, however:</p>
  
  <pre><code># DNA sequence generation also needs to be swapped to bytes
  tab_b = bytes.maketrans(b"ACTG", b"TGAC")
  
  def reverse_complement_bytes(seq):
      return seq.translate(tab_b)[::-1]
  </code></pre>
  
  <p>In my comparison:</p>
  
  <pre><code>Table implementation
         0.24339s total,
         2054315.7 strings per second
         82.5% increase over baseline
  Bytes table implementation
         0.14985s total,
         3336755.9 strings per second
         89.2% increase over table
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T16:57:57.957Z
Answers.Text: If one needs to convert back to string to interface with the rest of the code, what is the impact on speed ?
Answers.UserDisplayName: bli
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T17:04:52.547Z
Answers.Text: @bli It is still about 10% faster if you can work with bytes all the way through and then transfer to a string at the end. If you need to go string->bytes->string then it is about 25-30% slower than staying with strings
Answers.UserDisplayName: Jack Aidley
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T13:58:48.867Z
Answers.LastActivityDate: 2018-02-22T11:44:06.983Z
Answers.LastEditDate: 2018-02-22T11:44:06.983Z
Answers.UserDisplayName: Jack Aidley
Answers.Body: <p>The most reliable and simplest way is probably using <code>Biopython</code>:</p>
  
  <pre><code>from Bio.Seq import Seq
  
  def my_reverse_complement(seq):
      return Seq(seq).reverse_complement()
  
  print(my_reverse_complement('ATGCGTA'))
  # TACGCAT
  </code></pre>
  
  <p>As Devon has already <a href="https://bioinformatics.stackexchange.com/a/3585/104">said here</a> using <code>Biopython</code> isn't as fast as the naive Python solution, and I also tested that <a href="https://pastebin.com/Vupe6aQn" rel="nofollow noreferrer">shown here</a> with ipython. However, this is because <code>Biopython</code>'s implementation, although similar to the naive approach, includes other features; it can reverse complement RNA as well as DNA and it will tell you if you're mixing DNA and RNA</p>
  
  <p>Note that if you really want a fast way you could look at <code>Cython</code> or another python extension. As I edit this now, there are several nice answers taking this approach from user172818 and Alex Reynolds. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T14:01:55.927Z
Answers.Text: @JackAidley I mentioned in my own reply that biopython is ~50% slower than the naive code in the original post. It's good that this one actually included the code for that, though.
Answers.UserDisplayName: Devon Ryan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:04:05.030Z
Answers.LastActivityDate: 2018-02-21T22:36:42.120Z
Answers.LastEditDate: 2018-02-21T22:36:42.120Z
Answers.UserDisplayName: Chris_Rands
Answers.Body: <p>Since at least version <code>1.71</code> of biopython you can use <code>Bio.Seq.reverse_complement</code>, which also works on plain strings natively (no conversion to Seq objects).  On my mac I get 800k strings converted with that implementation ("biopython just rc") when using <a href="https://github.com/conchoecia/fastest_rc_python" rel="nofollow noreferrer">the benchmark</a>.</p>
  
  <pre><code>10000 strings and 250 repetitions
                           percent increase over baseline  seconds total strings per second
  name                                                                                     
  alexreynolds Cython (v2)                          94.0%       0.002491          4015188.7
  user172818 seqpy.c                                93.2%       0.002833          3529944.4
  alexreynolds Cython (v1)                          90.7%       0.003885          2573863.7
  devonryan string                                  86.0%       0.005804          1722983.5
  jackaidley bytes                                  85.7%       0.005959          1678085.3
  jackaidley bytesstring                            82.1%       0.007459          1340693.2
  biopython just rc                                 70.5%       0.012275           814638.6
  revcomp_translateSO                               49.9%       0.020822           480254.6
  revcom from SO                                    41.7%       0.024253           412320.2
  string_replace                                    35.2%       0.026946           371107.3
  lambda from SO                                    10.7%       0.037111           269464.0
  global dict                                        0.0%       0.041556           240641.7
  biopython seq then rc                            -30.9%       0.054430           183721.9
  naive (baseline)                                  -0.9%       0.041962           238313.6
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-06T20:37:38.893Z
Answers.LastActivityDate: 2018-04-09T11:04:41.833Z
Answers.LastEditDate: 2018-04-09T11:04:41.833Z
Answers.UserDisplayName: winni2k
Answers.Body: <pre><code>def revcomplement(s):
      s = s.upper()
      c = { &quot;A&quot;:&quot;T&quot;,&quot;C&quot;:&quot;G&quot;,&quot;T&quot;:&quot;A&quot;,&quot;G&quot;:&quot;C&quot;}
      co = str()
      for i in s:
          co = c[i] + co
      return co
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T14:09:24.447Z
Answers.Text: I don't think this piece of code actually "reverts" the sequence but just changes the bases with their complementary bases.
Answers.UserDisplayName: haci
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T14:15:41.573Z
Answers.Text: No it reverts the sequence and gives reverse complement.
Answers.UserDisplayName: amardeep
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T15:01:06.443Z
Answers.Text: My bad, `co = c[i] + co` does the trick. Could be useful if you run a benchmark along with the other offered solutions.
Answers.UserDisplayName: haci
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T18:56:04.097Z
Answers.Text: Thanks for joining the community Amardeep. I don't doubt that your code works, but I am a bit sceptical if it answers the original question (seeking for fastest solution). As a matter of fact, your solution is sort of included in the question already (reverse_complement_naive). There are plenty of questions that need to be answered, just make sure that you are really addressing what the person have asked :-)
Answers.UserDisplayName: Kamil S Jaron
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T11:49:02.593Z
Answers.Text: Sorry.  I implement what you said. Thanks
Answers.UserDisplayName: amardeep
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T13:54:27.530Z
Answers.LastActivityDate: 2020-11-08T15:01:38.253Z
Answers.LastEditDate: 2020-11-08T15:01:38.253Z
Answers.UserDisplayName: amardeep
Answers.Body: <p>I don't know if it's the fastest, but the following provides an approximately 10x speed up over your functions:</p>
  
  <pre class="lang-py prettyprint-override"><code>import string
  tab = string.maketrans("ACTG", "TGAC")
  
  def reverse_complement_table(seq):
      return seq.translate(tab)[::-1]
  </code></pre>
  
  <p>The thing with hashing is that it adds a good bit of overhead for a replacement set this small.</p>
  
  <p>For what it's worth, I added that to your code as "with a translation table" and here is what I got on my workstation:</p>
  
  <pre><code>global dict implementation
         1.37599s total,
         363374.8 strings per second
         3.3% increase over baseline
  naive implementation
         1.44126s total,
         346919.4 strings per second
         -1.3% increase over baseline
  with a translation table
         0.16780s total,
         2979755.6 strings per second
         88.2% increase over baseline
  </code></pre>
  
  <p>If you need python 3 rather than python 2, then substitute <code>tab = str.maketrans("ACTG", "TGAC")</code> for <code>tab = string.maketrans("ACTG", "TGAC")</code>, since <code>maketrans</code> is now a static method on the <code>str</code> type.</p>
  
  <p>For those wondering, using biopython is slower for this (~50% slower than the naive implementation), presumably due to the overhead of converting the strings to <code>Seq</code> objects. If one were already reading sequences in using biopython, though, I wouldn't be surprised if the performance was much different.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:14:25.637Z
Answers.Text: @Chris_Rands True, updated with the change needed for python3 (thankfully, it's only a single line difference).
Answers.UserDisplayName: Devon Ryan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T10:37:05.263Z
Answers.Text: Yeh, it''s `str.makestrans` though, `Biopython`'s implementation is pretty much the same but with some more alphabet and sanity checks https://github.com/biopython/biopython/blob/master/Bio/Seq.py#L860
Answers.UserDisplayName: Chris_Rands
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T07:34:17.150Z
Answers.LastActivityDate: 2018-02-20T21:36:01.947Z
Answers.LastEditDate: 2018-02-20T21:36:01.947Z
Answers.UserDisplayName: Devon Ryan
Body: <p>I am writing a python script that requires a reverse complement function to be called on DNA strings of length 1 through around length 30. Line profiling programs indicate that my functions spend a lot of time getting the reverse complements, so I am looking to optimize.</p>
  
  <p>What is the fastest way to get the reverse complement of a sequence in python? I am posting my skeleton program to test different implementations below with DNA string size 17 as an example.</p>
  
  <pre><code>#!/usr/bin/env python
  import random
  import timeit
  
  global complement
  complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
  
  DNAlength = 17
  
  #randomly generate 100k bases
  int_to_basemap = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
  num_strings = 500000
  random.seed(90210)
  DNAstrings = ["".join([int_to_basemap[random.randint(1,4)] for i in range(DNAlength)])
                for j in range(num_strings)]
  #get an idea of what the DNAstrings look like
  print(DNAstrings[0:5])
  
  def reverse_complement_naive(seq):
      this_complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
      return "".join(this_complement.get(base, base) for base in reversed(seq))
  
  def reverse_complement(seq):
      return "".join(complement.get(base, base) for base in reversed(seq))
  
  
  tic=timeit.default_timer()
  rcs = [reverse_complement_naive(seq) for seq in DNAstrings]
  toc=timeit.default_timer()
  baseline = toc - tic
  namefunc = {"naive implementation": reverse_complement_naive,
              "global dict implementation": reverse_complement}
  
  for function_name in namefunc:
      func = namefunc[function_name]
      tic=timeit.default_timer()
      rcs = [func(seq) for seq in DNAstrings]
      toc=timeit.default_timer()
      walltime = toc-tic
      print("""{}
         {:.5f}s total,
         {:.1f} strings per second
         {:.1f}% increase over baseline""".format(
             function_name,
             walltime,
             num_strings/walltime,
             100- ((walltime/baseline)*100)   ))
  </code></pre>
  
  <p>By the way, I get output like this. It varies by the call, of course!</p>
  
  <pre><code>naive implementation
         1.83880s total,
         271916.7 strings per second
         -0.7% increase over baseline
  global dict implementation
         1.74645s total,
         286294.3 strings per second
         4.3% increase over baseline
  </code></pre>
  
  <p>Edit: Great answers, everyone! When I get a chance in a day or two I will add all of these to a test file for the final run. When I asked the question, I had not considered whether I would allow for cython or c extensions when selecting the final answer. What do you all think?</p>
  
  <p>Edit 2: Here are the results of the final simulation with everyone's implementations. I am going to accept the highest scoring pure python code with no Cython/C. For my own sake I ended up using user172818's c implementation. If you feel like contributing to this in the future, <a href="https://github.com/conchoecia/fastest_rc_python" rel="noreferrer">check out the github page I made for this question</a>.</p>
  
  <pre><code>the runtime of reverse complement implementations.
  10000 strings and 250 repetitions
  ╔══════════════════════════════════════════════════════╗
  ║ name                       %inc   s total  str per s ║
  ╠══════════════════════════════════════════════════════╣
  ║ user172818 seqpy.c        93.7%  0.002344  4266961.4 ║
  ║ alexreynolds Cython (v2)  93.4%  0.002468  4051583.1 ║
  ║ alexreynolds Cython (v1)  90.4%  0.003596  2780512.1 ║
  ║ devonryan string          86.1%  0.005204  1921515.6 ║
  ║ jackaidley bytes          84.7%  0.005716  1749622.2 ║
  ║ jackaidley bytesstring    83.0%  0.006352  1574240.6 ║
  ║ global dict                5.4%  0.035330   283046.7 ║
  ║ revcomp_translateSO       45.9%  0.020202   494999.4 ║
  ║ string_replace            37.5%  0.023345   428364.9 ║
  ║ revcom from SO            28.0%  0.026904   371694.5 ║
  ║ naive (baseline)           1.5%  0.036804   271711.5 ║
  ║ lambda from SO           -39.9%  0.052246   191401.3 ║
  ║ biopython seq then rc    -32.0%  0.049293   202869.7 ║
  ╚══════════════════════════════════════════════════════╝
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-20T18:15:19.647Z
Comments.Text: You might also get some good advice from CodeReview.SE.
Comments.UserDisplayName: Sam Weaver
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-22T11:50:29.977Z
Comments.Text: Your implementation of my approach is not doing what I suggested. I suggested working with bytes instead of strings throughout. This means you need your DNAStrings to be in bytes instead of a string and so it would need a separate generation function.
Comments.UserDisplayName: Jack Aidley
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-22T15:29:04.653Z
Comments.Text: Ah, you meant use them for the entire program. I didn't think to do that. If I were to test that then I would need to convert the entire list of strings to bytestrings before testing, correct?
Comments.UserDisplayName: conchoecia
Tags: <python><phylogenetics><benchmarking>
Title: What is the fastest way to get the reverse complement of a DNA sequence in python?
ThreadText: # What is the fastest way to get the reverse complement of a DNA sequence in python?
  
  (Asked by: username_0 on 2018-02-20)
  
  I am writing a python script that requires a reverse complement function to be called on DNA strings of length 1 through around length 30. Line profiling programs indicate that my functions spend a lot of time getting the reverse complements, so I am looking to optimize.
  
  What is the fastest way to get the reverse complement of a sequence in python? I am posting my skeleton program to test different implementations below with DNA string size 17 as an example.
  
  ```
  #!/usr/bin/env python
  import random
  import timeit
  
  global complement
  complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
  
  DNAlength = 17
  
  #randomly generate 100k bases
  int_to_basemap = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
  num_strings = 500000
  random.seed(90210)
  DNAstrings = ["".join([int_to_basemap[random.randint(1,4)] for i in range(DNAlength)])
                for j in range(num_strings)]
  #get an idea of what the DNAstrings look like
  print(DNAstrings[0:5])
  
  def reverse_complement_naive(seq):
      this_complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
      return "".join(this_complement.get(base, base) for base in reversed(seq))
  
  def reverse_complement(seq):
      return "".join(complement.get(base, base) for base in reversed(seq))
  
  tic=timeit.default_timer()
  rcs = [reverse_complement_naive(seq) for seq in DNAstrings]
  toc=timeit.default_timer()
  baseline = toc - tic
  namefunc = {"naive implementation": reverse_complement_naive,
              "global dict implementation": reverse_complement}
  
  for function_name in namefunc:
      func = namefunc[function_name]
      tic=timeit.default_timer()
      rcs = [func(seq) for seq in DNAstrings]
      toc=timeit.default_timer()
      walltime = toc-tic
      print("""{}
         {:.5f}s total,
         {:.1f} strings per second
         {:.1f}% increase over baseline""".format(
             function_name,
             walltime,
             num_strings/walltime,
             100- ((walltime/baseline)*100)   ))
  
  ```
  
  By the way, I get output like this. It varies by the call, of course!
  
  ```
  naive implementation
         1.83880s total,
         271916.7 strings per second
         -0.7% increase over baseline
  global dict implementation
         1.74645s total,
         286294.3 strings per second
         4.3% increase over baseline
  
  ```
  
  Edit: Great answers, everyone! When I get a chance in a day or two I will add all of these to a test file for the final run. When I asked the question, I had not considered whether I would allow for cython or c extensions when selecting the final answer. What do you all think?
  
  Edit 2: Here are the results of the final simulation with everyone's implementations. I am going to accept the highest scoring pure python code with no Cython/C. For my own sake I ended up using username_6's c implementation. If you feel like contributing to this in the future, [check out the github page I made for this question](https://github.com/username_0/fastest_rc_python).
  
  ```
  the runtime of reverse complement implementations.
  10000 strings and 250 repetitions
  ╔══════════════════════════════════════════════════════╗
  ║ name                       %inc   s total  str per s ║
  ╠══════════════════════════════════════════════════════╣
  ║ username_6 seqpy.c        93.7%  0.002344  4266961.4 ║
  ║ username_3 Cython (v2)  93.4%  0.002468  4051583.1 ║
  ║ username_3 Cython (v1)  90.4%  0.003596  2780512.1 ║
  ║ username_5 string          86.1%  0.005204  1921515.6 ║
  ║ username_2 bytes          84.7%  0.005716  1749622.2 ║
  ║ username_2 bytesstring    83.0%  0.006352  1574240.6 ║
  ║ global dict                5.4%  0.035330   283046.7 ║
  ║ revcomp_translateSO       45.9%  0.020202   494999.4 ║
  ║ string_replace            37.5%  0.023345   428364.9 ║
  ║ revcom from SO            28.0%  0.026904   371694.5 ║
  ║ naive (baseline)           1.5%  0.036804   271711.5 ║
  ║ lambda from SO           -39.9%  0.052246   191401.3 ║
  ║ biopython seq then rc    -32.0%  0.049293   202869.7 ║
  ╚══════════════════════════════════════════════════════╝
  
  ```
  
  **Tags:** python, phylogenetics, benchmarking
  
  > **Comments:**
  > **username_1**: You might also get some good advice from CodeReview.SE.  
  > **username_2**: Your implementation of my approach is not doing what I suggested. I suggested working with bytes instead of strings throughout. This means you need your DNAStrings to be in bytes instead of a string and so it would need a separate generation function.  
  > **username_0**: Ah, you meant use them for the entire program. I didn't think to do that. If I were to test that then I would need to convert the entire list of strings to bytestrings before testing, correct?  
  
  ---
  
  ## 8 answers
  
  ### Answer by username_5 on 2018-02-20. Score: 23 | Accepted answer
  
  I don't know if it's the fastest, but the following provides an approximately 10x speed up over your functions:
  
  ```py
  import string
  tab = string.maketrans("ACTG", "TGAC")
  
  def reverse_complement_table(seq):
      return seq.translate(tab)[::-1]
  
  ```
  
  The thing with hashing is that it adds a good bit of overhead for a replacement set this small.
  
  For what it's worth, I added that to your code as "with a translation table" and here is what I got on my workstation:
  
  ```
  global dict implementation
         1.37599s total,
         363374.8 strings per second
         3.3% increase over baseline
  naive implementation
         1.44126s total,
         346919.4 strings per second
         -1.3% increase over baseline
  with a translation table
         0.16780s total,
         2979755.6 strings per second
         88.2% increase over baseline
  
  ```
  
  If you need python 3 rather than python 2, then substitute `tab = str.maketrans("ACTG", "TGAC")` for `tab = string.maketrans("ACTG", "TGAC")`, since `maketrans` is now a static method on the `str` type.
  
  For those wondering, using biopython is slower for this (~50% slower than the naive implementation), presumably due to the overhead of converting the strings to `Seq` objects. If one were already reading sequences in using biopython, though, I wouldn't be surprised if the performance was much different.
  
  > **Comments:**
  > **username_5**: @username_4 True, updated with the change needed for python3 (thankfully, it's only a single line difference).  
  > **username_4**: Yeh, it''s `str.makestrans` though, `Biopython`'s implementation is pretty much the same but with some more alphabet and sanity checks https://github.com/biopython/biopython/blob/master/Bio/Seq.py#L860  
  
  ---
  
  ### Answer by username_3 on 2018-02-20. Score: 9
  
  Here's a Cython approach that might suggest a generic approach to speeding up Python work.
  
  If you're manipulating (ASCII) character strings and performance is a design consideration, then C or Perl are probably preferred options to Python.
  
  In any case, this Cython test uses Python 3.6.3:
  
  ```
  $ python --version
  Python 3.6.3 :: Anaconda custom (64-bit)
  
  ```
  
  To install Cython, e.g.:
  
  ```
  $ conda install -c anaconda cython
  
  ```
  
  The Cython code below seems to offer about the same speed bump as the translation table — perhaps similar code is run under the hood of that.
  
  Two files are needed, starting with `setup.py`:
  
  ```
  from distutils.core import setup
  from Cython.Build import cythonize
  
  setup(
    name = 'Reverse complement C test',
    ext_modules = cythonize("revcomp_c.pyx"),
  )
  
  ```
  
  And then a second file called `revcomp_c.pyx`:
  
  ```
  from libc.stdlib cimport malloc
  
  cdef int seq_len = 17
  cdef char *seq_dest = <char *>malloc(seq_len + 1)
  seq_dest[seq_len] = '\0'
  
  def reverse_complement_c_v1(str seq):
      cdef bytes py_bytes = seq.encode('ascii')
      cdef char *seq_src = py_bytes
      cdef int i = 0
      cdef int d = 0
      for i in range(seq_len):
          d = seq_len - i - 1
          if seq_src[i] == 'A':
              seq_dest[d] = 'T'
          elif seq_src[i] == 'G':
              seq_dest[d] = 'C'
          elif seq_src[i] == 'C':
              seq_dest[d] = 'G'
          elif seq_src[i] == 'T':
              seq_dest[d] = 'A'
      return seq_dest[:seq_len].decode('ascii')
  
  ```
  
  This can be compiled into a Python module like so:
  
  ```
  $ python setup.py build_ext --inplace
  
  ```
  
  Then we can modify the test bench to include this Cython module and the relevant test method:
  
  ```
  #!/usr/bin/env python
  import random
  import timeit
  from revcomp_c import reverse_complement_c_v1
  
  global complement
  complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
  
  DNAlength = 17
  
  #randomly generate 100k bases
  int_to_basemap = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
  num_strings = 500000
  random.seed(90210)
  DNAstrings = ["".join([int_to_basemap[random.randint(1,4)] for i in range(DNAlength)])
                for j in range(num_strings)]
  #get an idea of what the DNAstrings look like
  print(DNAstrings[0:5])
  
  def reverse_complement_naive(seq):
      this_complement = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'}
      return "".join(this_complement.get(base, base) for base in reversed(seq))
  
  def reverse_complement(seq):
      return "".join(complement.get(base, base) for base in reversed(seq))
  
  tic=timeit.default_timer()
  rcs = [reverse_complement_naive(seq) for seq in DNAstrings]
  toc=timeit.default_timer()
  baseline = toc - tic
  namefunc = {"naive implementation": reverse_complement_naive,
              "global dict implementation": reverse_complement,
              "Cython implementation (v1)": reverse_complement_c_v1}
  
  for function_name in namefunc:
      func = namefunc[function_name]
      tic=timeit.default_timer()
      rcs = [func(seq) for seq in DNAstrings]
      toc=timeit.default_timer()
      walltime = toc-tic
      print("""{}
         {:.5f}s total,
         {:.1f} strings per second
         {:.1f}% increase over baseline""".format(
             function_name,
             walltime,
             num_strings/walltime,
             100- ((walltime/baseline)*100)   ))
  
  ```
  
  A sample run:
  
  ```
  $ python ./revcomp_test.py
  ['ACTGCAATAGACCACGC', 'CAGCTTGAGCCATTAAC', 'GGCCCAAGAGTTCGAAC', 'CGACTGTCTCGAATTGT', 'ATCCGCTATGCGCCGTC']
  naive implementation
         1.73295s total,
         288525.0 strings per second
         -2.5% increase over baseline
  global dict implementation
         1.70896s total,
         292575.5 strings per second
         -1.0% increase over baseline
  Cython implementation (v1)
         0.21458s total,
         2330158.7 strings per second
         87.3% increase over baseline
  
  ```
  
  One easy way to speed this up is to use a `static const unsigned char` array as an ASCII lookup table, which maps a residue directly to its complement. This would replace the nest of `if` statements and probably give a nice little boost ([and it appears it does, making it among the best performers so far!](https://bioinformatics.stackexchange.com/a/3595/776)).
  
  Here is my fast implementation of a reverse complement function in C:
  
  <https://gist.github.com/alexpreynolds/4f75cab4350e9d937f4a>
  
  You might be able to use this directly in Python via the `subprocess` library. Outsourcing the reverse complement step to a utility written in C will almost always beat the best that Python can do, and you can do nice and important things like bounds checking etc. without losing much speed.
  
  It's unclear how "pure" the answer needs to be, but making a system call from Python seems fair if you're processing strings and your goal is performance.
  
  Another direction to take may be to look at multithreading, if you don't need ordered output. If you have many thousands of sequences stored in memory, you could split an array of sequences up into smaller arrays by use of offsets or array indices. Each thread would work on "rc"-ing sequences in its own piece of the array.
  
  > **Comments:**
  > **username_4**: Nice, +1 for Cython  
  > **username_5**: Nice! Can you compare this to the `.translate()` version in my code? It'd be interesting to see how much Cython is able to speed things up in comparison given the general python overhead.  
  > **username_3**: @username_5: With this test bench, the "Cython implementation (v2)" on my Python 3 setup gave a 91.1% increase over baseline and "table" (translate) gave a 84.6% increase. I'm not sure how a Python 2 Cython setup compares.  
  
  ---
  
  ### Answer by username_4 on 2018-02-20. Score: 7
  
  The most reliable and simplest way is probably using `Biopython`:
  
  ```
  from Bio.Seq import Seq
  
  def my_reverse_complement(seq):
      return Seq(seq).reverse_complement()
  
  print(my_reverse_complement('ATGCGTA'))
  # TACGCAT
  
  ```
  
  As username_5 has already [said here](https://bioinformatics.stackexchange.com/a/3585/104) using `Biopython` isn't as fast as the naive Python solution, and I also tested that [shown here](https://pastebin.com/Vupe6aQn) with ipython. However, this is because `Biopython`'s implementation, although similar to the naive approach, includes other features; it can reverse complement RNA as well as DNA and it will tell you if you're mixing DNA and RNA
  
  Note that if you really want a fast way you could look at `Cython` or another python extension. As I edit this now, there are several nice answers taking this approach from username_6 and username_3.
  
  > **Comments:**
  > **username_5**: @username_2 I mentioned in my own reply that biopython is ~50% slower than the naive code in the original post. It's good that this one actually included the code for that, though.  
  
  ---
  
  ### Answer by username_6 on 2018-02-20. Score: 5
  
  Another python extension but without cython. The source code is available at the bottom of this answer or [from this gist](https://gist.github.com/attractivechaos/15a61b2517c253bb31bffcde3e45c6e8). On Mac with Python3:
  
  ```
  string
     0.38166s total,
     1310067.4 strings per second
     84.4% increase over baseline
  seqpy
     0.20524s total,
     2436182.7 strings per second
     91.6% increase over baseline
  
  ```
  
  On Linux with Python2 (seqpy is the first):
  
  ```
  seqpy  
     0.10960s total,
     4561842.5 strings per second
     93.3% increase over baseline
  string 
     0.17811s total,
     2807330.9 strings per second
     89.1% increase over baseline
  
  ```
  
  ---
  
  This is file `setup.py`:
  
  ```python
  from setuptools import setup, Extension
  
  seqpy_module = Extension('seqpy', sources = ["seqpy.c"])
  
  setup(
      name = "seqpy",
      description = "seqpy",
      ext_modules = [seqpy_module])
  
  ```
  
  This is file `seqpy.c`:
  
  ```c
  #include <stdlib.h>
  #include <stdint.h>
  #include <Python.h>
  
  static unsigned char seq_comp_table[256] = {
        0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
       16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
       32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
       48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
       64, 'T', 'V', 'G', 'H', 'E', 'F', 'C', 'D', 'I', 'J', 'M', 'L', 'K', 'N', 'O',
      'P', 'Q', 'Y', 'S', 'A', 'A', 'B', 'W', 'X', 'R', 'Z',  91,  92,  93,  94,  95,
       64, 't', 'v', 'g', 'h', 'e', 'f', 'c', 'd', 'i', 'j', 'm', 'l', 'k', 'n', 'o',
      'p', 'q', 'y', 's', 'a', 'a', 'b', 'w', 'x', 'r', 'z', 123, 124, 125, 126, 127,
      128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
      144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
      160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
      176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
      192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
      208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
      224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
      240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
  };
  
  static PyObject *seqpy_revcomp(PyObject *self, PyObject *args)
  {
      PyObject *r;
      char *seq, *rev;
      int i, len;
      PyArg_ParseTuple(args, "s#", &seq, &len);
      rev = (char*)malloc(len);
      for (i = 0; i < len; ++i)
          rev[len - i - 1] = seq_comp_table[(uint8_t)seq[i]];
      r = Py_BuildValue("s#", rev, len);
      free(rev);
      return r;
  }
  
  static PyMethodDef seqpy_methods[] = {
      {"revcomp", seqpy_revcomp, METH_VARARGS, "Reverse complement a DNA sequence"},
      {NULL, NULL, 0, NULL}
  };
  
  #if PY_MAJOR_VERSION >= 3
  static struct PyModuleDef seqpy_module = { PyModuleDef_HEAD_INIT, "seqpy", NULL, -1, seqpy_methods };
  PyMODINIT_FUNC PyInit_seqpy(void) { return PyModule_Create(&seqpy_module); }
  #else
  PyMODINIT_FUNC initseqpy(void) { Py_InitModule3("seqpy", seqpy_methods, NULL); }
  #endif
  
  ```
  
  To compile and test:
  
  ```
  python setup.py build_ext -i
  python -c 'import seqpy; print(seqpy.revcomp("GGGTT"))'
  
  ```
  
  
  ---
  
  ### Answer by username_3 on 2018-02-20. Score: 3
  
  Here is a revision of [my original Cython answer](https://bioinformatics.stackexchange.com/a/3587/776) which incorporates my suggestion to use a `char` lookup array:
  
  ```
  from libc.stdlib cimport malloc
  
  cdef int seq_len = 17
  cdef char *seq_dest = <char *>malloc(seq_len + 1)
  seq_dest[seq_len] = '\0'
  
  cdef char *basemap = [ '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',   '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  'T', '\0',  'G', '\0', '\0', '\0',  'C', '\0', '\0', '\0', '\0', '\0', '\0',  'N', '\0', '\0', '\0', '\0', '\0',  'A',  'A', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  't', '\0',  'g', '\0', '\0', '\0',  'c', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0',  'a',  'a' ]
  
  def reverse_complement_c_v2(str seq):
      cdef bytes py_bytes = seq.encode('UTF-8')
      cdef char *seq_src = py_bytes
      cdef int i = 0
      for i in range(seq_len):
          seq_dest[seq_len - i - 1] = basemap[<int>seq_src[i]]
      return seq_dest[:seq_len].decode('UTF-8')
  
  ```
  
  In testing under OS X, Python 3.6.3:
  
  ```
  $ python ./revcomp.py
  ['ACTGCAATAGACCACGC', 'CAGCTTGAGCCATTAAC', 'GGCCCAAGAGTTCGAAC', 'CGACTGTCTCGAATTGT', 'ATCCGCTATGCGCCGTC']
  ...
  Cython implementation (v1)
         0.20664s total,
         2419626.4 strings per second
         88.3% increase over baseline
  Cython implementation (v2)
         0.14170s total,
         3528668.5 strings per second
         92.0% increase over baseline
  
  ```
  
  Using my lookup array approach ("v2") adds a very decent performance bump over using `if` blocks ("v1"), and you can keep everything as a Python string.
  
  
  ---
  
  ### Answer by username_2 on 2018-02-20. Score: 3
  
  **Use a `bytearray` instead of a `string` and then employ `maketrans` to translate**
  
  You do not need the more advanced string encoding capabilities of `string` to store a string of bases, but you're still paying for it in performance. username_5 username_5's suggestion of `maketrans` is the huge improvement, 10x faster than your naive implementation. Using the same approach, but swapping everything out for `byte`s allows a further 40% speed improvement, however:
  
  ```
  # DNA sequence generation also needs to be swapped to bytes
  tab_b = bytes.maketrans(b"ACTG", b"TGAC")
  
  def reverse_complement_bytes(seq):
      return seq.translate(tab_b)[::-1]
  
  ```
  
  In my comparison:
  
  ```
  Table implementation
         0.24339s total,
         2054315.7 strings per second
         82.5% increase over baseline
  Bytes table implementation
         0.14985s total,
         3336755.9 strings per second
         89.2% increase over table
  
  ```
  
  > **Comments:**
  > **username_7**: If one needs to convert back to string to interface with the rest of the code, what is the impact on speed ?  
  > **username_2**: @username_7 It is still about 10% faster if you can work with bytes all the way through and then transfer to a string at the end. If you need to go string->bytes->string then it is about 25-30% slower than staying with strings  
  
  ---
  
  ### Answer by username_8 on 2018-04-06. Score: 2
  
  Since at least version `1.71` of biopython you can use `Bio.Seq.reverse_complement`, which also works on plain strings natively (no conversion to Seq objects). On my mac I get 800k strings converted with that implementation ("biopython just rc") when using [the benchmark](https://github.com/username_0/fastest_rc_python).
  
  ```
  10000 strings and 250 repetitions
                           percent increase over baseline  seconds total strings per second
  name                                                                                     
  username_3 Cython (v2)                          94.0%       0.002491          4015188.7
  username_6 seqpy.c                                93.2%       0.002833          3529944.4
  username_3 Cython (v1)                          90.7%       0.003885          2573863.7
  username_5 string                                  86.0%       0.005804          1722983.5
  username_2 bytes                                  85.7%       0.005959          1678085.3
  username_2 bytesstring                            82.1%       0.007459          1340693.2
  biopython just rc                                 70.5%       0.012275           814638.6
  revcomp_translateSO                               49.9%       0.020822           480254.6
  revcom from SO                                    41.7%       0.024253           412320.2
  string_replace                                    35.2%       0.026946           371107.3
  lambda from SO                                    10.7%       0.037111           269464.0
  global dict                                        0.0%       0.041556           240641.7
  biopython seq then rc                            -30.9%       0.054430           183721.9
  naive (baseline)                                  -0.9%       0.041962           238313.6
  
  ```
  
  
  ---
  
  ### Answer by username_9 on 2020-11-08. Score: 1
  
  ```
  def revcomplement(s):
      s = s.upper()
      c = { "A":"T","C":"G","T":"A","G":"C"}
      co = str()
      for i in s:
          co = c[i] + co
      return co
  
  ```
  
  > **Comments:**
  > **username_10**: I don't think this piece of code actually "reverts" the sequence but just changes the bases with their complementary bases.  
  > **username_9**: No it reverts the sequence and gives reverse complement.  
  > **username_10**: My bad, `co = c[i] + co` does the trick. Could be useful if you run a benchmark along with the other offered solutions.  
  > **username_11**: Thanks for joining the community username_9. I don't doubt that your code works, but I am a bit sceptical if it answers the original question (seeking for fastest solution). As a matter of fact, your solution is sort of included in the question already (reverse_complement_naive). There are plenty of questions that need to be answered, just make sure that you are really addressing what the person have asked :-)  
  > **username_9**: Sorry.  I implement what you said. Thanks  
  
  ---
  
  