PPubMed7 Mar 2024Cited 2×

Optimization and Performance Analysis of CAT Method for DNA Sequence Similarity Searching and Alignment

Veska Gancheva, Hristo Stoev, Clifford J. Steer

Abstract

Bioinformatics is a rapidly developing field enabling scientific experiments via computer models and simulations. In recent years, there has been an extraordinary growth in biological databases. Therefore, it is extremely important to propose effective methods and algorithms for the fast and accurate processing of biological data. Sequence comparisons are the best way to investigate and understand the biological functions and evolutionary relationships between genes on the basis of the alignment of two or more DNA sequences in order to maximize the identity level and degree of similarity. This paper presents a new version of the pairwise DNA sequences alignment algorithm, based on a new method called CAT, where a dependency with a previous match and the closest neighbor are taken into consideration to increase the uniqueness of the CAT profile and to reduce possible collisions, i.e., two or more sequence with the same CAT profiles. This makes the proposed algorithm suitable for finding the exact match of a concrete DNA sequence in a large set of DNA data faster. In order to enable the usage of the profiles as sequence metadata, CAT profiles are generated once prior to data uploading to the database. The proposed algorithm consists of two main stages: CAT profile calculation depending on the chosen benchmark sequences and sequence comparison by using the calculated CAT profiles. Improvements in the generation of the CAT profiles are detailed and described in this paper. Block schemes, pseudo code tables, and figures were updated according to the proposed new version and experimental results. Experiments were carried out using the new version of the CAT method for DNA sequence alignment and different datasets. New experimental results regarding collisions, speed, and efficiency of the suggested new implementation are presented. Experiments related to the performance comparison with Needleman-Wunsch were re-executed with the new version of the algorithm to confirm that we have the same performance.

A figure from Optimization and Performance Analysis of CAT Method for DNA Sequence Similarity Searching and Alignment — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

The new CAT method creates pre‑computed profiles that enable constant‑time DNA sequence alignment with negligible collisions and far faster than Needleman‑Wunsch.

What’s new

i.Introduced a revised CAT algorithm that uses previous match dependencies and nearest‑neighbor information to reduce profile collisions
ii.Implemented a two‑stage process: linear‑time CAT profile generation and constant‑time profile comparison (O(1))
iii.Demonstrated that CAT’s comparison time stays ~0.0004‑0.0007 s regardless of sequence length, vastly outperforming Needleman‑Wunsch and matching Knuth‑Morris‑Pratt speeds
iv.Provided an open‑source C# implementation and made the code publicly available on GitHub

How they did it

The authors first generate CAT profiles for each DNA sequence by comparing it against three fixed benchmark sequences, a step that runs in linear time O(n). Then, pairwise alignment is performed by computing Euclidean distances between the D and H parameters of the profiles, which runs in constant time (O(1)). Experiments used synthetic datasets of 100, 1 000, 10 000 and 50 000‑base sequences and measured execution times against Needleman‑Wunsch and Knuth‑Morris‑Pratt algorithms.

What they found

No collisions were observed in any of the tested sequence lengths
Average CAT comparison times: 0.0004025 s (len 100), 0.000466 s (len 1 000), 0.0007015 s (len 10 000), 0.0003645 s (len 50 000)
Needleman‑Wunsch times grew dramatically, e.g., 0.81 s (len 100) to 67 806 s (len 50 000)
Knuth‑Morris‑Pratt times were slower than CAT but much faster than Needleman‑Wunsch, e.g., 0.0025 s (len 100) to 1.48 s (len 50 000)

Caveats

✕Minor alignment deviations were reported, considered negligible only when permissible
✕The more accurate triangle‑area overlap improvement for stage 2 is proposed but not yet implemented
✕Experiments were conducted on synthetic sequences; performance on real biological datasets was not reported

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Optimization and Performance Analysis of CAT Method for DNA Sequence Similarity Searching and Alignment

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

The paper, in five minutes

Similar papers in all four archives