Related Experiment Video
Updated: Jul 7, 2026

16:24
Analyzing and Building Nucleic Acid Structures with 3DNA
Published on: April 26, 2013
Compressed indexing and local alignment of DNA.
1Department of Computer Science, University of Hong Kong, Hong Kong, China. twlam@cs.hku.hk
Bioinformatics (Oxford, England)
|January 30, 2008
Summary
This study introduces BWT-SW, a tool that uses Burrows-Wheeler Transform (BWT) indexes to efficiently find all local alignments in large biological sequences. BWT-SW significantly speeds up alignment discovery compared to traditional methods, aiding genomic research.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Compressed indexes like Burrows-Wheeler Transform (BWT) are practical for large string indexing (e.g., human genome).
- Existing methods for local alignment are too slow for genome-scale data or are heuristic and may miss alignments.
- Biologists need efficient tools to find local alignments with gaps in large biological sequences.
Purpose of the Study:
- To develop a practical software tool, BWT-SW, that leverages BWT indexes to accelerate the search for all local alignments.
- To provide a method for finding all local alignments in large texts, overcoming limitations of existing exact matching indexes and heuristic methods.
Main Methods:
- Exploiting a Burrows-Wheeler Transform (BWT) index of a text (T) to speed up dynamic programming for local alignment.
- Mathematical analysis of BWT-SW for a simplified similarity model (no gaps).
Main Results:
- BWT-SW demonstrates high efficiency, aligning a 3,000-character pattern with the human genome in under a minute.
- Mathematical analysis shows an expected running time of O(|T|/(0.628)/|P|) for random strings with gaps disallowed.
- BWT-SW is presented as the first practical tool capable of finding all local alignments.
Conclusions:
- BWT-SW offers a significant speedup for finding all local alignments in large biological sequences.
- While not a replacement for BLAST, BWT-SW provides a valuable tool for comprehensive alignment discovery and accuracy validation.
- The tool is available at www.cs.hku.hk/~ckwong3/bwtsw.
Related Concept Videos
DNA Packaging
Overview
Genomic DNA in Eukaryotes
Eukaryotes have large genomes compared to prokaryotes. To fit their genomes into a cell, eukaryotic DNA is packaged extraordinarily tightly inside the nucleus. To achieve this, DNA is tightly wound around proteins called histones, which are packaged into nucleosomes that are joined by linker DNA and coil into chromatin fibers. Additional fibrous proteins further compact the chromatin, which is recognizable as chromosomes during certain phases of cell division.
DNA Microarrays
Microarrays are high-throughput and relatively inexpensive assays that can be automated to analyze large quantities of data at a time. They are used in genome-wide studies to compare gene or protein expression under two varied conditions, such as healthy and diseased states. Microarrays consist of glass or silica slides on which probe molecules are covalently attached through surface functionalization. Most commonly, the slides are prepared through the chemisorption of silanes to silica...
The Nucleosome
Human DNA is almost two meters long. However, it is compressed inside a tiny nucleus measuring only a few microns in diameter. To make this degree of compaction possible, DNA is organized into several sequential levels so that it can fit into such a tiny space. The most compact form of DNA is a chromosome that can be seen under a microscope in a dividing cell.
In a chromosome, DNA is wound twice around a protein complex called a histone octamer core, which consists of 8 histone proteins. This...
In a chromosome, DNA is wound twice around a protein complex called a histone octamer core, which consists of 8 histone proteins. This...
DNA Isolation
DNA isolation protocols can be fast and straightforward or complex and time-consuming depending on the type and quality of DNA required for further processing. For example, plasmid DNA extraction is a bit more complicated than genomic DNA extraction because of the need for an appropriate lysis method to separate plasmid DNA from gDNA during isolation. However, for specific applications, such as long-range DNA sequencing that require a good yield of high- quality DNA samples, we need to follow...
RNA-seq
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...

