<p>I would suggest using a whole genome aligner like <a href="http://bio-bwa.sourceforge.net" rel="nofollow noreferrer">BWA</a> or <a href="http://bowtie-bio.sourceforge.net/bowtie2/" rel="nofollow noreferrer">BOWTIE2</a> and swapping out the whole genome reference with your specific reference.</p>
<p>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.</p>
<p>To ensure that local alignment is correct, keep in mind that <code>bowtie2</code> needs the <code>--local</code> while <code>bwa</code> should be run with on the <code>BWA-MEM</code> modality</p>

CC BY-SA 4.0
2018-08-20T14:28:45.690Z
2022-08-09T16:21:53.557Z
2022-08-09T16:21:53.557Z
Bioathlete
<p>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.</p>

<p>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. </p>

<p>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.</p>

<p><strong>So, to recap</strong>: 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!</p>

CC BY-SA 4.0
2018-08-19T10:48:14.827Z
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?
llrs
CC BY-SA 4.0
2018-08-19T11:56:51.207Z
@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.
Cedric Stroobandt
CC BY-SA 4.0
2018-08-19T15:36:44.023Z
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.
Bioathlete
CC BY-SA 4.0
2018-08-20T07:00:11.913Z
@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!
Cedric Stroobandt
CC BY-SA 4.0
2018-08-20T09:36:23.703Z
I have successfully used BWA and Bowtie2 for this sort of task, you may want to explore various parameters and how they affect the overall alignment rate.
Matt Bashton
CC BY-SA 4.0
2018-08-20T09:59:07.377Z
@Bioathlete you may as well post that as an answer so the question isn't left hanging.
terdon
<phylogenetics><ngs><algorithms>
Efficiently aligning a lot of reads on the same small reference sequence
# Efficiently aligning a lot of reads on the same small reference sequence

(Asked by: username_0 on 2018-08-19)

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!

**Tags:** phylogenetics, ngs, algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_0**: @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!  
> **username_3**: I have successfully used BWA and Bowtie2 for this sort of task, you may want to explore various parameters and how they affect the overall alignment rate.  
> **username_4**: @Bioathlete you may as well post that as an answer so the question isn't left hanging.  

---

## 1 answers

### Answer by username_2 on 2018-08-20. Score: 4 | Accepted answer

I would suggest using a whole genome aligner like [BWA](http://bio-bwa.sourceforge.net) or [BOWTIE2](http://bowtie-bio.sourceforge.net/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.

To ensure that local alignment is correct, keep in mind that `bowtie2` needs the `--local` while `bwa` should be run with on the `BWA-MEM` modality


---

