Adaptive seeds tame genomic sequence comparison

Abstract

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.

Keywords

BiologySequence (biology)Quadratic growthComposition (language)Computational biologyDNA sequencingAlgorithmGeneticsDNAComputer science

Affiliated Institutions

Related Publications

CDD: conserved domains and protein three-dimensional structure

Aron Marchler‐Bauer , Chanjuan Zheng , Farideh Chitsaz +15 more

CDD, the Conserved Domain Database, is part of NCBI's Entrez query and retrieval system and is also accessible via http://www.ncbi.nlm.nih.gov/Structure/cdd/cdd.shtml. CDD provi...

2012 Nucleic Acids Research 865 citations

VSEARCH: a versatile open source tool for metagenomics

Torbjørn Rognes , Tomáš Flouri , Ben Nichols +2 more

Background VSEARCH is an open source and free of charge multithreaded 64-bit tool for processing and preparing metagenomics, genomics and population genomics nucleotide sequence...

2016 PeerJ 10017 citations

Protein homology detection by HMM–HMM comparison

Johannes Söding

Abstract Motivation: Protein homology detection and sequence alignment are at the basis of protein structure prediction, function prediction and evolution. Results: We have gene...

2004 Bioinformatics 2470 citations

A New Algorithm for DNA Sequence Assembly

Ramana M. Idury , Michael S. Waterman

Since the advent of rapid DNA sequencing methods in 1976, scientists have had the problem of inferring DNA sequences from sequenced fragments. Shotgun sequencing is a well-estab...

1995 Journal of Computational Biology 344 citations

Assembling millions of short DNA sequences using SSAKE

Robin M. Warren , Granger G. Sutton , Steven J.M. Jones +1 more

Abstract Summary: Novel DNA sequencing technologies with the potential for up to three orders magnitude more sequence throughput than conventional Sanger sequencing are emerging...

2006 Bioinformatics 500 citations

Publication Info

Year: 2011
Type: article
Volume: 21
Issue: 3
Pages: 487-493
Citations: 1396
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Adaptive seeds tame genomic sequence comparison

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1396

OpenAlex

Cite This

APA Style

                            
                                
                                    Szymon M. Kiełbasa, 
                                
                                    Raymond Wan, 
                                
                                    Kengo Sato
                                
                                et al.
                            
                            (2011). 
                            Adaptive seeds tame genomic sequence comparison. 
                            Genome Research
                            , 21
                            (3)
                            , 487-493.
                            https://doi.org/10.1101/gr.113985.110
                        

Identifiers

DOI: 10.1101/gr.113985.110