Answers.Body: <p>As a rough and ready and very easy to perform test I would put the entire universe of dsDNA through Primer3 (details below). This could be done by "splicing" your probe of interest onto each "chunk" of dsDNA you pass through primer3 and restrict the primer search to the 20bp primer you are interested in. In other words you are forcing the program to consider the internal and trans-hybridisation of every possible dsDNA against your probe. If you probe is not recovered from a given search you would flag this on a subsequent parsing script and then that "chunk" of DNA would be assessed further. All the components required are in the link below. You would need to provide your own wrapper, but its fairly easy.</p>
  
  <p>Primer3 will assess the internal thermodynamics of your probe and it has loads of options to assess the full range of behaviour, for example 3' hybridisation (which could be extended because you want 5' to 3'). It would be easy to construct a parameter grid around all the parameters of interest. Ultimately it would provide an additional layer of certainty, and everyone knows and trusts this algorithm (its also written in C, so its fast). </p>
  
  <p>The description of all the components is <a href="https://bioinformatics.stackexchange.com/questions/8543/directed-mutagenesis-primer-design-by-back-to-back-pcr-of-constructs">here</a> , my specific purpose for customising the pipeline is different.</p>
  
  <hr>
  
  <p>Bowtie2 will take a lot of RAM, I am not sure I would use it for this purpose, particularly if RAM is limiting (its used for genome assemblies against a reference). I'd ask the users whether Blat would be useful, because that is friendlier to the calculation you are performing. Anyway there some heavy duty Bowtie2 users around and their input would be useful.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-04T12:47:34.303Z
Answers.Text: Thanks for the answer! I will definitely look into it. I am a little confused though. For example, I am not sure of the meaning of "entire universe of dsDNA". Right now I am simply generating a number of random ss probes (e.g. 10,000, avoiding homopolymers) and want to make sure that any two sequences will not form dsDNA (or dsDNA is acceptable up to a threshold, say 20%). I've been testing the resulting pairs (hence the n^2) with the workflow above. In your answer I see that your are referring to a single probe, however I need to consider the entire set? Apologies if I am missing the point.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-04T13:00:05.890Z
Answers.Text: My worthwhile idea is to use Primer3 as a benchmark against your your algorithm because Primer3 is a famous tool for generating oligonucleotides. You can then assess how well your approach is against Primer3 ... we all know this program so the comparison would be meaningful to us. The basic problem with your approach is that it isn't clear how to quantify 'success' purely in silico (its a problem of most bioinformatic predictions). Anyway I think its a cool idea.
Answers.UserDisplayName: M__
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-04T13:17:28.553Z
Answers.Text: " I've been testing the resulting pairs (hence the n^2) with the workflow above. In your answer I see that your are referring to a single probe, however I need to consider the entire set? "
  Primer3 will almost certainly perform that calculation, because it written in C its quick and it will select the output which best meets all the parameters. With regards your question, essentially 'yes' unless you have a heuristic search strategy. Its not hard to recursively assess all combinations and simply write increasing layers of abstraction if you have RAM problems (higher order programming)
Answers.UserDisplayName: M__
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-04T12:27:46.937Z
Answers.LastActivityDate: 2019-05-04T12:47:44.943Z
Answers.LastEditDate: 2019-05-04T12:47:44.943Z
Answers.UserDisplayName: M__
Body: <p>I am currently working on a Computer Science project where we are trying to build a large set of orthogonal single-stranded DNA sequences. The goal would be to ensure that when put in solution, the ssDNA do not interact with each other to form double-stranded DNA.</p>
  
  <p>I hope that this makes sense, but my knowledge  biological understanding is developing because I have a CS background. Please excuse any inadvertent errors.</p>
  
  <p>As one of the first steps, we used NUPACK to predict the percent of the resulting AB complex, given two single-stranded sequences A, B in concentration 1μM each. We would use the concentration of AB to classify if the strands are likely to form double-stranded DNA.</p>
  
  <p>However, we cannot use NUPACK for large sets, as we would need to do the above check against each of the other sequences, which is a quadratic problem. For a set of size 30,000 we would have to do 450 million NUPACK computations which is simply unfeasible.</p>
  
  <p>So I turned to the idea of approximating NUPACK. <a href="https://www.pnas.org/content/115/10/E2183" rel="nofollow noreferrer">In this paper</a>, it is claimed that </p>
  
  <blockquote>
    <p>Ideally, the thermodynamics of hybridization between a candidate
    probe and potential off-target sites would be modeled in
    silico and employed as a means of identifying probe oligos likely
    to only bind their intended targets in a given set of reaction
    conditions. Although powerful utilities such as NUPACK (52–
    54) are capable of performing such simulations, the limited
    throughput of these programs renders a direct thermodynamic
    approach impractical for genome-scale probe design. However,
    we hypothesized that features in rapidly calculated data such as
    alignment scores may be predictive of thermodynamic behavior
    and could therefore serve as a proxy for the information that
    would be produced by thermodynamic simulations.</p>
  </blockquote>
  
  <p><a href="https://i.sstatic.net/xb15Q.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xb15Q.png" alt="enter image description here"></a></p>
  
  <p>The alignment scores are then used to predict the interaction. <a href="http://bowtie-bio.sourceforge.net/bowtie2/index.shtml" rel="nofollow noreferrer">bowtie2</a> is used in the paper for alignment purposes. However, the context is different as their computation is done on genome information. Very sensitive settings of bowtie2 seem to be slow (hours) on my laptop and result in enormous files (tens of GB). I used less sensitive settings as a compromise but it seems to negatively affect the LDA.</p>
  
  <p>I am looking at alternative applications for alignment, but there are many alternatives (some of the more promising ones so far, in my opinion: <a href="http://snap.cs.berkeley.edu/" rel="nofollow noreferrer">SNAP</a>, <a href="https://github.com/soedinglab/MMseqs2" rel="nofollow noreferrer">MMseqs2</a>, <a href="https://github.com/felipealbrecht/Genoogle" rel="nofollow noreferrer">Genoogle</a>). Would any of these, or others not mentioned, be better suited for my purpose?</p>
  
  <p>Also any other advice or suggestions are welcome!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-04T12:09:40.233Z
Comments.Text: Welcome to the forum @David! Nice you are here and I like the question.
  My question is how long (bp) are you ss probes?
Comments.UserDisplayName: M__
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-04T12:14:40.937Z
Comments.Text: Thanks for the warm welcome! We are currently interested in 20bp.
Comments.UserDisplayName: David
Tags: <phylogenetics><fasta><blast><thermodynamics>
Title: Alignment for predicting DNA hybridization?
ThreadText: # Alignment for predicting DNA hybridization?
  
  (Asked by: username_0 on 2019-05-04)
  
  I am currently working on a Computer Science project where we are trying to build a large set of orthogonal single-stranded DNA sequences. The goal would be to ensure that when put in solution, the ssDNA do not interact with each other to form double-stranded DNA.
  
  I hope that this makes sense, but my knowledge biological understanding is developing because I have a CS background. Please excuse any inadvertent errors.
  
  As one of the first steps, we used NUPACK to predict the percent of the resulting AB complex, given two single-stranded sequences A, B in concentration 1μM each. We would use the concentration of AB to classify if the strands are likely to form double-stranded DNA.
  
  However, we cannot use NUPACK for large sets, as we would need to do the above check against each of the other sequences, which is a quadratic problem. For a set of size 30,000 we would have to do 450 million NUPACK computations which is simply unfeasible.
  
  So I turned to the idea of approximating NUPACK. [In this paper](https://www.pnas.org/content/115/10/E2183), it is claimed that
  
  > Ideally, the thermodynamics of hybridization between a candidate
  > probe and potential off-target sites would be modeled in
  > silico and employed as a means of identifying probe oligos likely
  > to only bind their intended targets in a given set of reaction
  > conditions. Although powerful utilities such as NUPACK (52–
  > 54) are capable of performing such simulations, the limited
  > throughput of these programs renders a direct thermodynamic
  > approach impractical for genome-scale probe design. However,
  > we hypothesized that features in rapidly calculated data such as
  > alignment scores may be predictive of thermodynamic behavior
  > and could therefore serve as a proxy for the information that
  > would be produced by thermodynamic simulations.
  
  [![enter image description here](https://i.sstatic.net/xb15Q.png)](https://i.sstatic.net/xb15Q.png)
  
  The alignment scores are then used to predict the interaction. [bowtie2](http://bowtie-bio.sourceforge.net/bowtie2/index.shtml) is used in the paper for alignment purposes. However, the context is different as their computation is done on genome information. Very sensitive settings of bowtie2 seem to be slow (hours) on my laptop and result in enormous files (tens of GB). I used less sensitive settings as a compromise but it seems to negatively affect the LDA.
  
  I am looking at alternative applications for alignment, but there are many alternatives (some of the more promising ones so far, in my opinion: [SNAP](http://snap.cs.berkeley.edu/), [MMseqs2](https://github.com/soedinglab/MMseqs2), [Genoogle](https://github.com/felipealbrecht/Genoogle)). Would any of these, or others not mentioned, be better suited for my purpose?
  
  Also any other advice or suggestions are welcome!
  
  **Tags:** phylogenetics, fasta, blast, thermodynamics
  
  > **Comments:**
  > **username_1**: Welcome to the forum @username_0! Nice you are here and I like the question. My question is how long (bp) are you ss probes?  
  > **username_0**: Thanks for the warm welcome! We are currently interested in 20bp.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-04. Score: 1
  
  As a rough and ready and very easy to perform test I would put the entire universe of dsDNA through Primer3 (details below). This could be done by "splicing" your probe of interest onto each "chunk" of dsDNA you pass through primer3 and restrict the primer search to the 20bp primer you are interested in. In other words you are forcing the program to consider the internal and trans-hybridisation of every possible dsDNA against your probe. If you probe is not recovered from a given search you would flag this on a subsequent parsing script and then that "chunk" of DNA would be assessed further. All the components required are in the link below. You would need to provide your own wrapper, but its fairly easy.
  
  Primer3 will assess the internal thermodynamics of your probe and it has loads of options to assess the full range of behaviour, for example 3' hybridisation (which could be extended because you want 5' to 3'). It would be easy to construct a parameter grid around all the parameters of interest. Ultimately it would provide an additional layer of certainty, and everyone knows and trusts this algorithm (its also written in C, so its fast).
  
  The description of all the components is [here](https://bioinformatics.stackexchange.com/questions/8543/directed-mutagenesis-primer-design-by-back-to-back-pcr-of-constructs) , my specific purpose for customising the pipeline is different.
  
  ---
  
  Bowtie2 will take a lot of RAM, I am not sure I would use it for this purpose, particularly if RAM is limiting (its used for genome assemblies against a reference). I'd ask the users whether Blat would be useful, because that is friendlier to the calculation you are performing. Anyway there some heavy duty Bowtie2 users around and their input would be useful.
  
  > **Comments:**
  > **username_0**: Thanks for the answer! I will definitely look into it. I am a little confused though. For example, I am not sure of the meaning of "entire universe of dsDNA". Right now I am simply generating a number of random ss probes (e.g. 10,000, avoiding homopolymers) and want to make sure that any two sequences will not form dsDNA (or dsDNA is acceptable up to a threshold, say 20%). I've been testing the resulting pairs (hence the n^2) with the workflow above. In your answer I see that your are referring to a single probe, however I need to consider the entire set? Apologies if I am missing the point.  
  > **username_1**: My worthwhile idea is to use Primer3 as a benchmark against your your algorithm because Primer3 is a famous tool for generating oligonucleotides. You can then assess how well your approach is against Primer3 ... we all know this program so the comparison would be meaningful to us. The basic problem with your approach is that it isn't clear how to quantify 'success' purely in silico (its a problem of most bioinformatic predictions). Anyway I think its a cool idea.  
  > **username_1**: " I've been testing the resulting pairs (hence the n^2) with the workflow above. In your answer I see that your are referring to a single probe, however I need to consider the entire set? " Primer3 will almost certainly perform that calculation, because it written in C its quick and it will select the output which best meets all the parameters. With regards your question, essentially 'yes' unless you have a heuristic search strategy. Its not hard to recursively assess all combinations and simply write increasing layers of abstraction if you have RAM problems (higher order programming)  
  
  ---
  
  