LAST seeding schemes ==================== LAST's critical first step is to find *seeds*, i.e. initial matches between query and reference sequences. It can use various seeding schemes, which allow different kinds of mismatches at different seed positions. A seeding scheme consists of a seed alphabet, such as:: 1 A C G T 0 ACGT T AG CT and one or more patterns, such as this one:: 1T1T10T1101101 Each symbol in a pattern represents a grouping of sequence letters: in this example, ``T`` represents the grouping ``AG CT``. At each position in an initial match, mismatches are allowed between letters that are grouped at that position in the pattern. Although the patterns have fixed lengths, LAST's initial matches do not. LAST finds shorter matches by using a prefix of the pattern, and longer matches by cyclically repeating the pattern. A *restricted* symbol omits letters of the main sequence alphabet, which are then forbidden at those positions:: r AG An *exact* symbol groups no letters:: Y C T In 2nd and subsequent cycles, restricted symbols are made unrestricted: if it is exact then the omitted letters are added as separate groups, else they are added as one group. BISF ---- This seeding scheme is for aligning bisulfite-converted DNA *forward* strands to a closely-related genome (MC Frith, R Mori, K Asai, NAR 2012 40:e100). It uses this seed alphabet:: 1 CT A G 0 ACGT And this pattern:: 1111110101100 It sets this lastdb default: -w2 It sets this lastal default: -pBISF BISR ---- This seeding scheme is for aligning bisulfite-converted DNA *reverse* strands to a closely-related genome (MC Frith, R Mori, K Asai, NAR 2012 40:e100). It uses this seed alphabet:: 1 AG C T 0 ACGT And this pattern:: 1111110101100 It sets this lastdb default: -w2 It sets this lastal default: -pBISR MAM4 ---- This DNA seeding scheme is like MAM8, but a bit less sensitive, and uses about half as much memory. [From Frith & Noé 2014 NAR 42:e59 Table S11, row 12.] It uses this seed alphabet:: 1 A C G T 0 ACGT T AG CT And these patterns:: 11100TT01T00T10TTTT TTTT110TT0T001T0T1T1 11TT010T01TT0001T 11TT10T1T101TT MAM8 ---- This DNA seeding scheme finds weak similarities with high sensitivity, but low speed and high memory usage (e.g. ~50 GB for mammal genomes). [From Frith & Noé 2014 NAR 42:e59 Table S12, row 15.] It uses this seed alphabet:: 1 A C G T 0 ACGT T AG CT And these patterns:: 1101T1T0T1T00TT1TT 1TTTTT010TT0TT01011TTT 1TTTT10010T011T0TTTT1 111T011T0T01T100 1T10T100TT01000TT01TT11 111T101TT000T0T10T00T1T 111100T011TTT00T0TT01T 1T1T10T1101101 MURPHY10 -------- This protein seeding scheme is popular for finding long-and-weak similarities (LR Murphy et al. Protein Eng. 2000 13:149). It uses this seed alphabet:: 1 ILMV FWY A C G H P KR ST DENQ And this pattern:: 1 It sets this lastdb default: -p NEAR ---- This DNA seeding scheme is good for finding short-and-strong (near-identical) similarities. It is also good for similarities with many gaps (insertions and deletions), because it can find the short matches between the gaps. (Long-and-weak seeding schemes allow for mismatches but not gaps.) It uses this seed alphabet:: 1 A C G T 0 ACGT And this pattern:: 1111110 It sets this lastal default: -r6 -q18 -a21 -b9 PSEUDO ------ This seeding scheme slightly increases sensitivity of DNA-versus-protein search for pseudogenes. It uses this seed alphabet:: 1 A C D E F G H I K L M N P Q R S T V W Y * 0 ACDEFGHIKLMNPQRSTVWY* 2 ACST DEN FHWY G KQR* P ILMV And this pattern:: 1120 YASS ---- This DNA seeding scheme is good for finding long-and-weak similarities. It is a good compromise for both protein-coding and non protein-coding DNA (L Noé & G Kucherov, NAR 2005 33:W540-W543). It uses this seed alphabet:: 1 A C G T 0 ACGT T AG CT And this pattern:: 1T1001100101 RY4-9 (abbreviation: RY4) ------------------------- This DNA seeding scheme reduces run time and memory use, by only seeking seeds at ~1/4 of positions in each sequence. (From "How to optimally sample a sequence for rapid analysis" by MC Frith, J Shaw, JL Spouge.) It uses this seed alphabet:: R A G Y C T And these patterns:: RRRRRRRRY RRRRRRYRY RRRRRYRRR RRRRRYRRY RRRRRYYRR RRRRRYYRY RRRRRYYYR RRRRRYYYY RRRYRYRRR RRRYRYRRY RRRYRYYRR RRRYRYYRY RRRYRYYYR RRRYRYYYY RRYRRRRRR RRYRRRRRY RRYRRRYRY RRYRRYRRR RRYRRYRRY RRYRRYRYR RRYRRYYRR RRYRRYYRY RRYRRYYYY RRYRYRYRY RRYYRYRRR RRYYRYRRY RRYYRYYRY RRYYRYYYY RRYYYYRRR RRYYYYRRY RRYYYYRYR RRYYYYYRR RYRRRRYRR RYRRRRYRY RYRRRRYYR RYRRRRYYY RYRRRYRRR RYRRRYRRY RYRRRYYRR RYRRRYYRY RYRRRYYYR RYRRRYYYY RYRRYRYYR RYRRYRYYY RYRRYYYRR RYRRYYYRY RYRYRYRRR RYRYRYRRY RYRYRYYRR RYRYRYYRY RYRYRYYYR RYRYRYYYY RYYRRRRRR RYYRRRRRY RYYRRRRYR RYYRRRYRR RYYRRRYRY RYYRRRYYR RYYRRRYYY RYYRRYRRR RYYRRYRRY RYYRRYRYR RYYRRYYRR RYYRRYYRY RYYRRYYYR RYYRRYYYY RYYRYRYRR RYYRYRYRY RYYRYRYYR RYYRYRYYY RYYRYYRRR RYYRYYRRY RYYRYYYRR RYYRYYYRY RYYYRYRRR RYYYRYRRY RYYYRYYRR RYYYRYYRY RYYYRYYYR RYYYRYYYY RYYYYRYYR RYYYYRYYY RYYYYYRYR RYYYYYYRR RYYYYYYYY YRYRRRRRR YRYRRRRRY YRYRRRYRY YRYRRYRRR YRYRRYRRY YRYRRYRYR YRYRRYYRR YRYRRYYRY YRYRRYYYY YRYYRYRRR YRYYRYRRY YRYYRYYRY YRYYRYYYY YRYYYYRRR YRYYYYRRY YRYYYYRYR YRYYYYYRR YYRRRRYYR YYRRRRYYY YYRRYRYYR YYRRYRYYY YYYRRRRRR YYYRRRRRY YYYRRRRYR YYYRRRYRR YYYRRRYRY YYYRRRYYR YYYRRRYYY YYYRRYRRR YYYRRYRRY YYYRRYRYR YYYRRYYRR YYYRRYYRY YYYRRYYYR YYYRRYYYY YYYRYRYRR YYYRYRYRY YYYRYRYYR YYYRYRYYY YYYYYRYYR YYYYYRYYY YYYYYYRYR YYYYYYYRR It sets this lastal default: -m2 -r6 -q18 -a21 -b9 RY8-10 (abbreviation: RY8) -------------------------- This DNA seeding scheme reduces run time and memory use, by only seeking seeds at ~1/8 of positions in each sequence. (From "How to optimally sample a sequence for rapid analysis" by MC Frith, J Shaw, JL Spouge.) It uses this seed alphabet:: R A G Y C T And these patterns:: RRRRYRRRRY RRRRYRRRYR RRRRYRRRYY RRRRYRYRRY RRRRYRYRYY RRRRYYRRYY RRRRYYYRYY RRRYRRRRRR RRRYRRRRRY RRRYRRYRRY RRRYRRYRYY RRRYYRRRRY RRRYYRRRYR RRRYYRRRYY RRRYYRRYRY RRRYYRYRRY RRRYYRYRYY RRRYYYRRRR RRRYYYRRRY RRRYYYRRYY RRRYYYYRYY RRYRYRRRRR RRYRYRRRRY RRYRYRRRYR RRYRYRRRYY RRYRYRYRRR RRYRYRYRRY RRYRYRYRYR RRYRYRYRYY RRYRYYRRYY RRYRYYYRYY RRYYRRRRRY RRYYRRYRRR RRYYRRYRRY RRYYRYRRRR RRYYRYRRRY RRYYRYRYRR RRYYRYRYRY RRYYRYYRYY RRYYYRRYRR RRYYYRRYRY RRYYYRYRRY RRYYYRYRYY RRYYYYRRRR RRYYYYRRRY RRYYYYRRYR RRYYYYRRYY RRYYYYRYRR RRYYYYRYRY RRYYYYYRRY RRYYYYYRYY RRYYYYYYRY RYRRYRRRRR RYRRYRRRRY RYRRYRRRYR RYRRYRRRYY RYRRYRYRRY RYRRYRYRYY RYRRYYRRYY RYRRYYYRYY RYRYYRRRRY RYRYYRRRYR RYRYYRRRYY RYRYYRRYRY RYRYYRYRRY RYRYYRYRYY RYRYYYRRYY RYRYYYYRYY RYYRRRRRRR RYYRRRRRRY RYYRYYRRYY RYYRYYYRYY RYYYRYRRRR RYYYRYRRRY RYYYRYRYRR RYYYRYRYRY RYYYYYRRRR RYYYYYRRRY RYYYYYRYRR RYYYYYRYRY RYYYYYYRRR RYYYYYYRRY RYYYYYYYRY YRRYYRRRRY YRRYYRRRYR YRRYYRRRYY YRRYYRRYRY YRRYYRYRRY YRRYYRYRYY YRRYYYRRRR YRRYYYRRRY YRRYYYRRYY YRRYYYYRYY YRYYRRRRRY YRYYRRYRRR YRYYRRYRRY YRYYRYRRRR YRYYRYRRRY YRYYRYRYRR YRYYRYRYRY YRYYYRRRRR YRYYYRRRRY YRYYYRRRYR YRYYYRRRYY YRYYYRRYRR YRYYYRRYRY YRYYYRYRRY YRYYYRYRYY YRYYYYRRRR YRYYYYRRRY YRYYYYRRYR YRYYYYRRYY YRYYYYRYRR YRYYYYRYRY YRYYYYYRRY YRYYYYYRYY YRYYYYYYRY YYRYYRRRRY YYRYYRRRYR YYRYYRRRYY YYRYYRRYRY YYRYYRYRRY YYRYYRYRYY YYRYYYRRYY YYRYYYYRYY YYYYYYYRRR YYYYYYYRRY YYYYYYYYRY It sets this lastal default: -m2 -r6 -q18 -a21 -b9 RY16-11 (abbreviation: RY16) ---------------------------- This DNA seeding scheme reduces run time and memory use, by only seeking seeds at ~1/16 of positions in each sequence. (From "How to optimally sample a sequence for rapid analysis" by MC Frith, J Shaw, JL Spouge.) It uses this seed alphabet:: R A G Y C T And these patterns:: RRYRYRRRRRR RRYRYRRRRYR RRYRYRRRYRR RRYRYRRYRRR RRYRYRRYRRY RRYRYRYRRRR RRYRYRYRRYR RRYRYRYRYRR RRYRYRYYRRR RRYRYRYYRRY RRYRYYRRRRR RRYRYYRRRYR RRYRYYRRYRR RRYRYYRYRRY RRYRYYYRRRR RRYRYYYRRYR RRYRYYYRYRR RRYRYYYYRRR RRYRYYYYRRY RRYYRRRRRRR RRYYRRRRRRY RRYYRRRRRYR RRYYRRRRYRR RRYYRRRYRRR RRYYRRRYRRY RRYYRRYRRRR RRYYRRYRRRY RRYYRRYRRYR RRYYRYRRRRR RRYYRYRRRRY RRYYRYRRRYR RRYYRYRRYRR RRYYRYRYRRR RRYYRYRYRRY RRYYRYRYYRR RRYYRYYRRRR RRYYRYYRRRY RRYYRYYRRYR RRYYRYYYRRR RRYYRYYYRRY RRYYRYYYYRR RRYYYRRRRRR RRYYYRRRRRY RRYYYRRRRYR RRYYYRRRYRR RRYYYRRYRRR RRYYYRRYRRY RRYYYRYRRRR RRYYYRYRRRY RRYYYRYRRYR RRYYYRYYRRR RRYYYRYYRRY RRYYYRYYYRR RRYYYYRRRRR RRYYYYRRRRY RRYYYYRRRYR RRYYYYRRYRR RRYYYYRYRRR RRYYYYRYRRY RRYYYYRYYRR RRYYYYYRRRR RRYYYYYRRRY RRYYYYYRRYR RRYYYYYRYRR RRYYYYYYRRY RYRYRYRYYRR RYRYRYYYRRR RYRYRYYYRRY RYRYRYYYYRR RYRYYRYRRRR RYRYYRYRRRY RYRYYRYRYRR RYRYYRYYRRR RYRYYRYYRRY RYRYYRYYYRR RYRYYYRYYRR RYRYYYYRYRR RYRYYYYYRRR RYRYYYYYRRY RYYRYYRYRRR RYYRYYRYRRY RYYRYYYRYRR RYYYRYRYRRR RYYYRYRYRRY RYYYRYRYYRR RYYYRYYRYRR RYYYYRYRYRR RYYYYYRYYRR RYYYYYYRRRR RYYYYYYRRRY RYYYYYYRYRR RYYYYYYYRRR RYYYYYYYRRY RYYYYYYYYRR YRYRYRYRYRR YRYRYYRYRRY YRYRYYYRYRR YRYYRYRYYRR YRYYRYYYYRR YRYYYRYYYRR YRYYYYRYYRR YRYYYYYRYRR YRYYYYYYRRY YYRYRYRYRRR YYRYRYRYRRY YYRYRYRYYRR YYRYRYYYRRR YYRYRYYYRRY YYRYRYYYYRR YYRYYRYRYRR YYRYYRYYRRR YYRYYRYYRRY YYRYYRYYYRR YYRYYYRYYRR YYRYYYYRYRR YYRYYYYYRRR YYRYYYYYRRY YYYRYYYRYRR YYYRYYYYRRR YYYRYYYYRRY YYYYRYRYYRR YYYYRYYRYRR YYYYRYYYRRR YYYYRYYYRRY YYYYYRYRYRR YYYYYYRYYRR YYYYYYYRYRR YYYYYYYYYRR It sets this lastal default: -m2 -r6 -q18 -a21 -b9 RY32-12 (abbreviation: RY32) ---------------------------- This DNA seeding scheme reduces run time and memory use, by only seeking seeds at ~1/32 of positions in each sequence. (From "How to optimally sample a sequence for rapid analysis" by MC Frith, J Shaw, JL Spouge.) It uses this seed alphabet:: R A G Y C T And these patterns:: RRRRRRRRYYYR RRRRRRRRYYYY RRRRRRYRRYYY RRRRRRYRYYYR RRRRRYRRRYYY RRRRRYRYYYYR RRRRRYRYYYYY RRRRRYYRYYYR RRRRRYYRYYYY RRRRYRYRRYYY RRRRYRYRYYYR RRRRYRYRYYYY RRRRYRYYRYYY RRRRYYRRYYYR RRRRYYRRYYYY RRRRYYRYRYYY RRRYRRRRYYYR RRRYRRRRYYYY RRRYRRYRYYYR RRRYRRYRYYYY RRRYYRRRRYYY RRRYYRRRYYYR RRRYYRYRRYYY RRRYYRYYRYYY RRYRRRRRRYYY RRYRRRRRYYYR RRYRRRYRYYYR RRYRRRYRYYYY RRYRRRYYRYYY RRYRRYRRRYYY RRYRRYRRYYYR RRYRRYRRYYYY RRYRRYYRRYYY RRYRRYYRYYYR RRYRRYYRYYYY RRYRYRRRRYYY RRYRYRRRYYYR RRYRYRRRYYYY RRYRYRRYRYYY RRYRYRYRRYYY RRYRYRYRYYYR RRYRYRYRYYYY RRYRYYRRRYYY RRYRYYRRYYYR RRYRYYRRYYYY RRYYRRRRRYYY RRYYRRRYRYYY RRYYRRRYYYYR RRYYRRRYYYYY RRYYRRYRYYYR RRYYRRYRYYYY RRYYRYRYRYYY RRYYRYYRRYYY RYRRRRRRRYYY RYRRRRRYYYYR RYRRRRRYYYYY RYRRRRYRRYYY RYRRRRYRYYYR RYRRRRYRYYYY RYRRRRYYRYYY RYRRRYRRRYYY RYRRRYRRYYYR RYRRRYRRYYYY RYRRRYRYRYYY RYRRRYYRRYYY RYRRYRRRRYYY RYRRYRRYRYYY RYRRYRYRRYYY RYRRYRYRYYYR RYRRYRYRYYYY RYRRYRYYRYYY RYRRYYRYRYYY RYRYRRRYRYYY RYRYRRYRRYYY RYRYRRYYRYYY RYRYRYRRRYYY RYRYRYRYRYYY RYRYRYYRRYYY RYRYRYYRYYYR RYRYRYYRYYYY RYRYYRRRRYYY RYRYYRRYRYYY RYRYYRYRRYYY RYRYYRYRYYYR RYRYYRYRYYYY RYRYYRYYRYYY RYYRRRRRRYYY RYYRRRRYRYYY RYYRRRYRRYYY RYYRRRYYRYYY RYYRRYRRRYYY RYYRRYRRYYYR RYYRRYRRYYYY RYYRRYRYRYYY RYYRRYYRRYYY RYYRRYYRYYYR RYYRRYYRYYYY RYYRYRRRRYYY RYYRYRRRYYYR RYYRYRRRYYYY RYYRYRRYRYYY RYYRYRYRRYYY RYYRYRYYRYYY RYYRYYRRRYYY RYYRYYRYRYYY YRRRRRYRRYYY YRRRRRYRYYYR YRRRRYRRRYYY YRRRYRYRRYYY YRRRYRYYRYYY YRRRYYRYRYYY YRRYYRRRRYYY YRRYYRRRYYYR YRRYYRYRRYYY YRRYYRYYRYYY YRYRRRRRRYYY YRYRRRRRYYYR YRYRRRYYRYYY YRYRRYRRRYYY YRYRRYYRRYYY YRYRYRRRRYYY YRYRYRRYRYYY YRYRYRYRRYYY YRYRYYRRRYYY YRYYRRRRRYYY YRYYRRRYRYYY YRYYRYRYRYYY YRYYRYYRRYYY It sets this lastal default: -m2 -r6 -q18 -a21 -b9 RY64-13 (abbreviation: RY64) ---------------------------- This DNA seeding scheme reduces run time and memory use, by only seeking seeds at ~1/64 of positions in each sequence. It uses this seed alphabet:: R A G Y C T And these patterns:: RRRRRRRRRRYYY RRRRRRRRYRYYY RRRRRRYRRYYYY RRRRRRYRYRYYY RRRRRRYYRYYYY RRRRRYRRRRYYY RRRRRYYRRRYYY RRRRRYYRRYYYY RRRRRYYRYRYYY RRRRYRRRRRYYY RRRRYRRRYRYYY RRRRYRRYRRYYY RRRRYRRYRYYYY RRRRYRYRRRYYY RRRRYRYYRYYYY RRRRYYRRRRYYY RRRRYYRRYRYYY RRRRYYRYRRYYY RRRYRRRYRRYYY RRRYRRRYYRYYY RRRYRRYRYRYYY RRRYRRYYRRYYY RRRYRRYYRYYYY RRRYRYRRYRYYY RRRYRYRYRRYYY RRRYRYRYRYYYY RRRYRYRYYRYYY RRRYYRYRYRYYY RRYRRRRYRYYYY RRYRRRRYYRYYY RRYRRRYRYRYYY RRYRRYRRRRYYY RRYRRYRRRYYYY RRYRYRRRRRYYY RRYRYRRRRYYYY RRYRYRRRYRYYY RRYRYRRYRRYYY RRYRYYRRRYYYY RRYRYYRRYYYYY RRYRYYRYRRYYY RRYRYYRYRYYYY RRYRYYRYYRYYY RRYYRRRRYRYYY RRYYRRRYRYYYY RRYYRRRYYRYYY RRYYRRYRRRYYY RRYYRRYRRYYYY RRYYRYRRRRYYY RRYYRYRYRRYYY RRYYRYRYYRYYY RYRRRRRRRRYYY RYRRRRRRRYYYY RYRRRRRRYRYYY RYRRRRRYRRYYY RYRRRRRYRYYYY RYRRRRRYYRYYY RYRRRRYRRYYYY RYRRRRYRYRYYY RYRRRRYYRRYYY RYRRRYRRRRYYY RYRRRYRRRYYYY RYRRRYRRYRYYY RYRRRYRYRRYYY RYRRRYYRRRYYY RYRRRYYRRYYYY RYRRRYYRYRYYY RYRRYRRRRRYYY RYRRYRRRYRYYY RYRRYRRYRYYYY RYRRYRRYYRYYY RYRRYRYRRRYYY RYRRYRYRRYYYY RYRRYRYRYRYYY RYRRYRYYRYYYY RYRRYYRRRRYYY RYRRYYRRRYYYY RYRRYYRRYRYYY RYRRYYRYRRYYY RYRRYYRYRYYYY RYRRYYRYYRYYY RYRYRRRRRRYYY RYRYRRRRYRYYY RYRYRRRYRRYYY RYRYRRRYYRYYY RYRYRRYRRRYYY RYRYRRYRYRYYY RYRYRRYYRRYYY RYRYRYRRRYYYY RYRYRYRYRRYYY RYRYRYRYRYYYY RYRYRYRYYRYYY RYRYRYYRRRYYY RYRYRYYRRYYYY RYRYRYYRYRYYY RYRYYRRRRYYYY RYRYYRRRYRYYY RYRYYRRYRRYYY RYRYYRRYYRYYY RYRYYRYRRRYYY RYRYYRYYRRYYY RYYRRRRRRRYYY RYYRRRRRRYYYY RYYRRRRRYRYYY RYYRRRRRYYYYY RYYRRRRYYRYYY RYYRRRYRRRYYY RYYRRRYRRYYYY RYYRRRYRYRYYY RYYRRRYYRRYYY RYYRRYRRRRYYY RYYRRYRRYRYYY RYYRRYRYRRYYY RYYRRYRYRYYYY RYYRRYRYYRYYY RYYRRYYRRYYYY RYYRRYYRYRYYY RYYRYRRRRRYYY RYYRYRRRYRYYY RYYRYRRYRRYYY RYYRYRRYRYYYY RYYRYRRYYRYYY RYYRYRYRRRYYY RYYRYRYRYRYYY RYYRYYRRRRYYY RYYRYYRRYRYYY RYYRYYRYRRYYY RYYRYYRYRYYYY RYYRYYRYYRYYY It sets this lastal default: -m2 -r6 -q18 -a21 -b9