Related Experiment Video
Updated: Jun 15, 2026
14:06
Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER
Published on: June 23, 2012
Localized suffix array and its application to genome mapping problems for paired-end short reads.
1Central Research Laboratory, Hitachi Ltd, 1-280 Higashi-Koigakubo, Kokubunji, Tokyo 185-8601, Japan. kouichi.kimura.hh@hitachi.com
Genome Informatics. International Conference on Genome Informatics
|February 25, 2010
Summary
A new localized suffix array data structure improves text search efficiency by combining global position and local order. This accelerates paired word searches, especially in repetitive genomic data.
Area of Science:
- Computer Science
- Bioinformatics
- Data Structures
Background:
- Efficient text search is crucial for applications like genome mapping.
- Conventional suffix arrays can be slow for queries involving word pairs and distance constraints.
- Repetitive sequences in genomic data pose significant computational challenges.
Purpose of the Study:
- To introduce a novel data structure, the localized suffix array, for enhanced text search.
- To improve the efficiency of searching for word pairs within a specified distance.
- To apply this new structure to accelerate genome mapping of paired-end short reads.
Main Methods:
- Developed a localized suffix array that dynamically represents occurrence information.
- Combined global positional and local lexicographic order information.
- Implemented a search strategy that progressively refines positional resolution and re-examines distance constraints.
Main Results:
- The localized suffix array offers a memory footprint comparable to conventional suffix arrays.
- Demonstrated significant speedups (over 10x) in genome mapping for repetitive paired-end reads.
- Achieved efficiency gains in cases with high read redundancy (sums of occurrences > 2,000).
Conclusions:
- The localized suffix array provides an efficient method for paired word searches with distance constraints.
- This data structure is particularly beneficial for analyzing repetitive genomic data from next-generation sequencing.
- The approach offers a practical solution for accelerating bioinformatics pipelines.
Related Concept Videos
03:21RNA-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...
01:57Sanger Sequencing
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
01:17Karyotyping
Describing the number and physical features of chromosomes can reveal abnormalities that underlie genetic diseases. This description is facilitated by special staining techniques that produce a particular banding pattern on each chromosome. State-of-the-art techniques make this approach even more powerful, enabling the detection of individual genes that cause disease.A Simple Chromosome Staining Technique Provides Valuable Scientific InsightSome genetic diseases can be detected by looking at...
03:00Next-generation Sequencing
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
03:36Genome Annotation and Assembly
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
02:34DNA 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...