Faster computation of left-bounded shortest unique substrings.

Area of Science:

• String processing algorithms
• Bioinformatics applications
• Computational biology

Background:

• Shortest Unique Substrings (SUS) is a key problem in string processing.
• Applications include bioinformatics, such as DNA sequence analysis.
• A specific variant, Left-Bounded Shortest Unique Substrings (LSUS), is vital for PCR primer design.

Purpose of the Study:

• To present a novel, efficient algorithm for the LSUS problem.
• To address the need for faster computational methods in bioinformatics.
• To provide a practical solution for PCR primer design challenges.

Main Methods:

• Developed a linear time O(n) algorithm for LSUS.
• Utilized 2n memory words plus n bytes for input strings.
• Algorithm designed for efficient string processing.

Main Results:

• Achieved O(n) time complexity.
• Demonstrated practical speed improvements, averaging two times faster than related methods.
• Maintained a comparable peak memory footprint to existing algorithms.

Conclusions:

• The presented LSUS algorithm is highly efficient in terms of time complexity.
• Offers practical advantages for bioinformatics tasks, especially PCR primer design.
• Represents a significant advancement in solving the LSUS problem efficiently.