4
$\begingroup$

The context: I have a DNA-sequence coding for a protein, about 1500 bp in length. Using NGS, a lot of reads of (mutants of) this same sequence were acquired. All of these reads need to be aligned to the reference. We're talking about a lot of reads (100,000 - 1,000,000) of not too short length (120 - 300 bp). All of these reads can belong to different mutants of the template sequence, so the alignment is necessary to determine the exact sequence of every single mutant.

Currently, I'm just using Smith-Waterman-based local alignment to align every single read to the reference one by one. Yet I can't help but feel there might be a more computationally/time-efficient solution to this specific problem.

Maybe there exists an algorithm that's not very efficient for most alignment problems, but that becomes very worthwile if it has to map a ton of reads to the same place over and over again. For example, it might do some time-consuming operations on the short template that make it fast to align reads to it, but these operations aren't worth it if only aligning a couple of reads. That's just an idea, I don't know all the different techniques that are out there.

So, to recap: I want to align a lot (100,000 - 1,000,000) of 120-300 bp reads to the same short 1500 bp reference sequence. If anyone has any suggestions about an algorithm, or just a specific workflow, that is particularly suited to do this, it would be appreciated. I work in R so I can implement some things myself, it doesn't have to be a ready-to-use software package or anything like that. Thanks in advance!

$\endgroup$
  • $\begingroup$ Have you tried using some multi sequence alignments tools like T-coffe, or clustal? How many time are you willing to spend/how much accuracy do you want? Do you know which reads belong to each single mutant or is all in a pool? $\endgroup$ – llrs Aug 19 '18 at 10:48
  • $\begingroup$ @Llopis: yes, it is known which reads belong to the same mutant. I haven't used multi sequence alignment because I don't want to align all sequences to eachother, as I'm only interested in differences with the reference. As for time: at this moment it's still manageable to use common local alignment algorithms like Smith-Waterman, but if there's an approach that's just faster than this, it will help in the scale-up to even more high-throughput. $\endgroup$ – Cedric Stroobandt Aug 19 '18 at 11:56
  • 2
    $\begingroup$ Have you tried using whole genome aligners like BWA and BOWTIE2 with your custom reference? These are designed for NGS input and alignment of larger numbers or reads against a single reference. $\endgroup$ – Bioathlete Aug 19 '18 at 15:36
  • $\begingroup$ @Bioathlete: No, I haven't tried it yet because BWA and BOWTIE2 were indeed designed for "whole genomes" while my reference is extremely small. I wondered if there were any methods that were commonly used in that case. Maybe not, and BWA or BOWTIE might still be the optimal choice, even for a small reference. That's as good an answer as any. I'll wait a little longer for extra suggestions, otherwise I'll consider the question answered. Thanks! $\endgroup$ – Cedric Stroobandt Aug 20 '18 at 7:00
  • 2
    $\begingroup$ @Bioathlete you may as well post that as an answer so the question isn't left hanging. $\endgroup$ – terdon Aug 20 '18 at 9:59
4
$\begingroup$

I would suggest using a whole genome aligner like BWA or BOWTIE2 and swapping out the whole genome reference with your specific reference.

These alignment algorithms are designed to align large numbers of NGS reads against a single reference. They can be used with any reference including short ones like your example or small viruses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.