Adaptive seeds tame genomic sequence comparison.

By S. Kiełbasa, Raymond Wan, Kengo Sato, Paul Horton, Martin C. Frith. 2011

1,235 citations recorded by the source corpus.

The main way of analyzing biological sequences is by comparing and aligning them to each other. It remains difficult, however, to compare modern multi-billionbase DNA data sets. The difficulty is caused by the nonuniform (oligo)nucleotide composition of these sequences, rather than their size per se. To solve this problem, we modified the standard seed-and-extend approach (e.g., BLAST) to use adaptive seeds. Adaptive seeds are matches that are chosen based on their rareness, instead of using fixed-length matches. This method guarantees that the number of matches, and thus the running time, increases linearly, instead of quadratically, with sequence length. LAST, our open source implementation of adaptive seeds, enables fast and sensitive comparison of large sequences with arbitrarily nonuniform composition.

Subfields: Artificial Intelligence, Molecular Biology, Computational Biology & Bioinformatics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Computational Biology & Bioinformatics

Citations in the corpus

MMseqs2: sensitive protein sequence searching for the analysis of massive data sets (2017, methodology): “standard BLAST tool [2] has mostly been replaced by faster and less sensitive search tools such as BLAT[17], UBLAST[6], LAST[18], RAPSearch2[30], and DIAMOND[4].”
One chromosome, one contig: complete microbial genomes from long-read sequencing and assembly. (2015, methodology): “Web BLAST [87] was run with default options for ‘Somewhat similar sequences’ in all cases except for Oxford, which was aligned with last [88]: lastal -r 1 -q 1 -a 1 -b 1 -Q 0 -j 3 -f 1 ecoli.”
The IMG/M data management and analysis system v.6.0: new tools and advanced capabilities (2020, methodology): “Best LAST hits between CDSs and IMG reference proteomes derived from high quality public genomes are computed for placing the sequences in phylogenetic context through Phylogenetic Distribution of Best Hits tool.”
IMG/M v.5.0: an integrated data management and comparative analysis system for microbial genomes and microbiomes (2018, methodology): “1 (15), assignment to a subset of InterPro families using a customized version of InterProScan5 (16) and associating proteins with KEGG Orthology (KO) terms (17) using LAST (18).”
Piercing the dark matter: bioinformatics of long-range sequencing and mapping (2018, methodology): “Commonly used methods to perform the whole-genome alignment include MUMmer 79 or LAST 80 , followed by methods such as AsmVar 66 or Assemblytics 81 to scan the alignments for SVs.”
Structural variant calling: the long and the short of it (2019, methodology): “NanoSV preferentially uses as input an alignment from LAST [96], which uses adaptive seed rather than fixed-length seed for speed optimization [96].”
Unicycler: Resolving bacterial genome assemblies from short and long sequencing reads (2016, methodology): “MG1655 reference genome’s seven RNA operons in the assemblies using BLAST.”
Robust taxonomic classification of uncharted microbial sequences and bins with CAT and BAT (2019, methodology): “Recently, the MEGAN long read algorithm was introduced17, which partitions the sequence into intervals based on the location of hits of a LAST18 search.”
PhyloSift: phylogenetic analysis of genomes and metagenomes (2014, methodology): “This is important because it reduces the volume of sequence to search and because part of LAST’s fast heuristic to identify candidate regions to align involves eliminating redundant and repetitive k-mers from the search space (Kiełbasa et al., 2011).”
Reagent and laboratory contamination can critically impact sequence-based microbiome analyses (2014, methodology): “Similarity sequencing for taxonomic assignments was performed using LAST in six-frame translation mode against the Microbial RefSeq protein database [71].”