LAST home | LAST web service | CBRC home

LAST is like BLAST, only:

• It can handle big sequence data. With LAST, you can:
  • Compare two vertebrate genomes
  • Map lots of DNA reads to a genome
  • Compare a genome to all known proteins
  It is hard or impossible to do these things with BLAST.
• LAST can tell you which parts of an alignment are reliable, and which parts are inherently unreliable.

Here are some dotplots made using LAST:

• Human vs. mouse. This took about 1 day on 1 CPU, and less than 2 GB of RAM.
• Drosophila melanogaster vs. Drosophila pseudoobscura. This took about 30 minutes and less than 1 GB of RAM.

Why would you use LAST to map DNA reads, when there are dozens of specialized tools for that task?

• Because LAST is not specialized, it can map arbitrarily long reads, with arbitrarily many mismatches and gaps. "Like BLAST, only it works."
• LAST can gain accuracy by taking sequence quality data into account, while also allowing for real sequence differences (from polymorphisms, or cross-species mapping). Few specialized tools can do both of these things.

LAST is not related to LASTZ. The similar name is a coincidence.

The documents in the LAST download can be viewed here: the main one is last-manual.txt, and there is an interesting table of optimal spaced seeds for tag mapping in tag-seeds.txt. Here are some slides (pdf) that give an introduction to sequence comparison and LAST.

The main technical innovation is that LAST finds initial matches based on their multiplicity, instead of using a fixed length (e.g. BLAST uses 11-mers). This allows us to map reads to genomes without repeat-masking, without becoming overwhelmed by repetitive hits. To find these variable-length matches, it uses a suffix array (inspired by Vmatch). To achieve high sensitivity, it uses a spaced suffix array (or subset suffix array), analogous to spaced seeds (or subset seeds).

Publications:

• Incorporating sequence quality data into alignment improves DNA read mapping. MC Frith, R Wan, P Horton, NAR 2010.
• Parameters for accurate genome alignment. MC Frith, M Hamada, P Horton, BMC Bioinformatics 2010.

Development:

• Trac.
• Change log.
• Browse the repository.
• Check it out using Subversion: svn co http://last.cbrc.jp/last