Alignment for predicting DNA hybridization? 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, 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.




The alignment scores are then used to predict the interaction. bowtie2 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, MMseqs2, Genoogle). Would any of these, or others not mentioned, be better suited for my purpose?

Also any other advice or suggestions are welcome!
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 , 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.