Related Experiment Videos
The position end-set tree: a small automaton for word recognition in biological sequences
1Genosphere Project, ERATO, JRDC, Tokai University School of Medicine, Kanagawa, Japan.
Computer Applications in the Biosciences : CABIOS
|June 1, 1993
Summary
This study introduces a new method for efficiently searching for substrings within long sequences. The developed compact index, a type of automaton, speeds up repetitive searches and aids in sequence analysis software development.
Area of Science:
- Computer Science
- Bioinformatics
- Algorithm Design
Background:
- Substring searching is a fundamental operation in sequence analysis.
- Efficiently locating patterns within large datasets is crucial for many applications.
- Existing methods may require significant computational resources for repeated searches.
Purpose of the Study:
- To propose a novel method for constructing a compact index to accelerate substring searches.
- To develop an efficient, on-line algorithm for index generation.
- To enable faster and more interactive sequence analysis.
Main Methods:
- Construction of a compact index represented as a partial deterministic finite automaton.
- Development of a linear-time, on-line algorithm for index generation.
- Utilizing the index for efficient subword localization.
Main Results:
- A compact index is generated in linear time.
- The index effectively recognizes the subword structure of a sequence.
- Subword localization is performed efficiently using the proposed data structure.
Conclusions:
- The proposed compact index and construction algorithm significantly enhance substring search efficiency.
- This method is valuable for developing interactive sequence analysis tools.
- The approach offers a practical solution for managing and analyzing large sequences.