according to the different algorithm that responsible for alignment sequences and the changes form one to another because each algorithm may not achieve the best accuracy while the others not achieve the best speed for this alignment , I asked if it is a new or existing algorithm that achieve the both the accuracy and the speed at the same time?
For NGS read mapping to a reference genome you may want to consider NextGenMap (or NGM) - a mapper that is as accurate as Stampy and faster than Bowtie2 and BWA. See http://cibiv.github.io/NextGenMap/ and http://dx.doi.org/10.1093/bioinformatics/btt468 for more information.
It is a trade-off between finding the "optimal" solution and the fastest solution... Finding a faster solution involves employing some sort of heuristic.. For example in a maximum likelihood tree search, most algorithms do not exhaustively search all possible topologies, as this would take forever, but instead they explore tree space with a heuristic method which makes it possible to exclude certain paths of branch swaps (etc) which seem to yield suboptimal trees. And so the end result is not guaranteed to be the best tree in tree space, but instead to be the best tree of all explored paths. Or at least that's my understanding of it.
So, shortcuts have to be taken to make the algorithm more practical... As processor speed and parallel capabilities increase, I guess we will see more use of exhaustive searches. Someone may come along who knows more though.
Take for example the clustering algorithm used by Usearch. In order to cluster sequences which match above some identity threshold (calculated by alignment), they do not make every possible pairwise comparison in order to determine cluster membership, but instead use a heuristic- by ordering the search (or pairwise comparisons) by the number of matching "words" (k-mers; substrings of k length). By ordering sequences to align like this, the most optimal solution will tend to be in the first few elements of this sorted list. But you are not guaranteed to find the "best" match... Unless the assumption (which we use for narrowing our comparisons down) that matching sequences will tend to share more k-mers than less optimal matches always holds... The expectation being that the assumption will on average hold, and suboptimal cluster assignments will be minimized, while also minimizing the amount of time that would be spent (certainly a good trade-off vs exhaustively making all pairwise checks)...
In my opinion, "best" accuracy and "best" speed are probably incompatible, since guaranteeing the "best" solution every time would exclude the use of a heuristic. Although in practice we can see "better" accuracy together with "better" speed- by being efficient, and using smart heuristics (or example MUSCLE tends to be faster than ClustalW, yet often yields better alignments).... The idea being that we tend towards the most accurate solution in the least time possible...
That being said, the existing algorithms can be pretty fast. I have had good experience with MUSCLE and ClustalO (omega), and also Vsearch for NGS read clustering+alignment. What sort of data are you aligning?
Thank you for your answer.
I studied about the sequence alignment for next-generation sequencing that used algorithms based on BLAST , Hash-tables and suffix and I infer that it may be an alternative algorithm that provides the speed and accuracy together at the same time
Your answer covered all things about my question , thank you
I second Tyler's comments about MUSCLE. I have used it frequently and found it to yield good accuracy at good speed.
For NGS read mapping to a reference genome you may want to consider NextGenMap (or NGM) - a mapper that is as accurate as Stampy and faster than Bowtie2 and BWA. See http://cibiv.github.io/NextGenMap/ and http://dx.doi.org/10.1093/bioinformatics/btt468 for more information.
You could also check out Teaser: http://teaser.cibiv.univie.ac.at/
Its a framework to benchmark mappers giving your own parameter and reference settings. Eg. benchmarking 5 mappers on a human genome data set requires around 20 min. There is the online version, but also an offline version that allows you much more.
Depending upon what you want to do with the alignments later - I would also recommend using the SSW implementation of Smith-Waterman. (https://github.com/mengyao/Complete-Striped-Smith-Waterman-Library). It is the fastest implementation of smith waterman alignment that I have seen till date and can do a standard alignment as well as a SAM output which is useful with multiple downstream analysis pipelines.
Also if you are comfortable with Python - this algorithm has been optimally implemented in the scikit-bio package.
@Rahul: Interesting, is it a full SW or a bandit?
I have done something similar back then: a library for CUDA, OpenCL banded SW:
http://www.cibiv.at/software/ngm/mason/
@Fritz thank you so much for that. I have been looking for an OpenCL implementation of SW for a while now! I will be sure to give it a shot.. Are you able to port your libraries as apps or to python libraries? If that were the case then it would be mighty useful given most people run SW's as a part of automated pipelines these days.. ^_^
SSW or (pySSW) I believe is strictly banded SW and not GPU optimised as far as I know. I just love it because of the python libraries - fits in with pipelines like a charm and the CIGAR strings are super useful in analysis.
No we "just" have a C++ library. Should be easy though to get a python interface in front of that. The SSW seems to be fast on the forward step, but kind of slow on the backtracking.
Thanks for all these answers
depends on these different choices and answers I can infer that the best choice using "Muscle" to get the best speed and accuracy at the same time
this thing will also reduce the effort and the cost for work , test and evaluate many of algorithms to get both speed and accuracy if it is found by using one algorithm
- Badges
- Science method
- Similar topics
- Biological Science
- Genetics
- Genetic Analysis
- genetic techniques
- Sequencing