Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-20T14:28:45.690Z
Answers.LastActivityDate: 2022-08-09T16:21:53.557Z
Answers.LastEditDate: 2022-08-09T16:21:53.557Z
Answers.UserDisplayName: Bioathlete
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-19T10:48:14.827Z
Comments.Text: 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?
Comments.UserDisplayName: llrs
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-19T11:56:51.207Z
Comments.Text: @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.
Comments.UserDisplayName: Cedric Stroobandt
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-19T15:36:44.023Z
Comments.Text: 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.
Comments.UserDisplayName: Bioathlete
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-20T07:00:11.913Z
Comments.Text: @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!
Comments.UserDisplayName: Cedric Stroobandt
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-20T09:36:23.703Z
Comments.Text: 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.
Comments.UserDisplayName: Matt Bashton
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-20T09:59:07.377Z
Comments.Text: @Bioathlete you may as well post that as an answer so the question isn't left hanging.
Comments.UserDisplayName: terdon
Tags: <phylogenetics><ngs><algorithms>
Title: Efficiently aligning a lot of reads on the same small reference sequence
ThreadText: # 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**: @username_2: 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**: @username_2 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
  
  
  ---
  
  