I would like to know what is meant by "seed" for various sequence aligners. How is it important?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The seed is the subset of a read used in the first step of an alignment. Many aligners work by a seed-and-extend model, wherein they first find all regions matching the "seed" and then extend the alignment around that allowing mistmatches and indels until it either gives up (and therefore uses a different seed) or finds a sufficiently good alignment.
answered Mar 16, 2019 at 12:52
-
$\begingroup$ Thanks devon for the explanation. I have a slightly similar question as to why finding a seed for a very short exons is difficult? Considering a 3 nt exon, is it because seed such small has a probability of mapping every 4^3=64 bases and virtually impossible to look for in the genome? Your views on this $\endgroup$ Mar 17, 2019 at 21:12
-
$\begingroup$ Usually seeds are a few times that length, since you want few enough hits to limit your search space quickly. $\endgroup$ Mar 17, 2019 at 22:04
$\begingroup$
$\endgroup$
Devon's answer gives a good, concise definition. But it's also helpful to consider why seed-and-extend is used and what benefits it provides.
Finding approximate string matches requires operations that are expensive computationally. On the other hand, finding exact string matches can be performed using much less expensive operations—that is, it can be done more quickly with less memory. So quickly finding the location of all seed matches and then applying the approximate matching ONLY AT THOSE LOCATIONS (the seed-and-extend strategy) makes sure that less time is wasted on chasing spurious similarities.
So how long should a seed be? Riffing off your comment, a seed 3bp in length would be entirely ineffective since that same 3bp sequence is going to occur ALL OVER THE GENOME IN RANDOM PLACES: genes, pseudogenes, transposable elements, regulatory sequences, you name it. On the other hand, a seed 51bp in length would also be ineffective since almost every seed would contain at least one sequencing error or variant/polymorphism, thus preventing a perfect match.
In practice, mappers designed for aligning 100-300bp Illumina reads typically use seeds in the high teens or low 20s.