Suffix tree searcher: exploration of common substrings in large DNA sequence sets

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Analyzing large DNA sequence datasets requires specialized bioinformatics tools for efficient searching and comparison.
• Previous suffix tree implementations were limited by memory constraints, hindering accessibility for researchers.
• Existing fast suffix tree algorithms lacked graphical user interfaces, impeding integration into laboratory workflows.

Purpose of the Study:

• To develop an easy-to-use bioinformatics tool for indexing, searching, and analyzing very large DNA sequence datasets.
• To overcome the limitations of previous suffix tree implementations by incorporating disk-based approaches and a graphical user interface.

Main Methods:

• Implementation of Suffix Tree Searcher (STS) with a Java-based graphical user interface and C modules.
• Utilizing pre-sorted persistent "building blocks" to optimize suffix tree construction.
• Employing disk-based approaches to handle datasets exceeding available RAM.

Main Results:

• STS accommodates extremely large DNA sequence datasets, reaching tens of billions of nucleotides.
• The tool enables rapid searching of nucleotide strings with support for wildcards and mismatches.
• Complete tree traversals for detecting common substrings are performed efficiently.

Conclusions:

• STS provides a novel resource for identifying common substrings within and across massive DNA sequences.
• The software facilitates efficient evaluation of nucleotide sequence similarity through advanced search and retrieval capabilities.
• The graphical user interface ensures user-friendliness, rapid data access, and seamless workflow integration.