TSTA: thread and SIMD-based trapezoidal pairwise/multiple sequence-alignment method Authors: Peiyu Zong, Wenpeng Deng, Jian Liu, Jue Ruan, zong peiyu, Scott Edmunds, Hongfang Zhang, Christopher Hunter, Xingbao Song, Yuansheng Liu, Hongfang Zhang, zong peiyu, Hongfang Zhang, Yuansheng Liu, Hongfang Zhang, zong peiyu, Hongfang Zhang, Yuansheng Liu, Hongfang Zhang, zong peiyu, Hongfang Zhang, Christopher Hunter, Hongfang Zhang, Scott Edmunds, Scott Edmunds Published: 2024 ABSTRACT AbstractThe rapid advancements in sequencing length necessitate the adoption of increasingly efficient sequence alignment algorithms. The Needleman–Wunsch method introduces the foundational dynamic-programming matrix calculation for global alignment, which evaluates the overall alignment of sequences. However, this method is known to be highly time-consuming. The proposed TSTA algorithm leverages both vector-level and thread-level parallelism to accelerate pairwise and multiple sequence alignments.Availability and implementationSource codes are available at https://github.com/bxskdh/TSTA. Introduction Sequence alignment is a crucial foundation of bioinformatics, playing a vital role in the analysis of biological sequence data. Currently, the Smith–Waterman algorithm [1] and the Needleman–Wunsch algorithm [2] are the most commonly used for sequence comparison. These algorithms calculate the maximum score for each cell in a dynamic programming (DP) matrix and track the optimal source path. Gotoh [3] later improved these algorithms by introducing an affine gap penalty, which extends the linear gap penalty used in the original algorithms and allows for a more focused gap representation. Although all three algorithms succeed in achieving optimal alignment results, they require significant computational time when applied to lengthy sequences. Various optimization techniques have been developed to enhance the efficiency of sequence alignment. Single instruction multiple data (SIMD) A highly effective approach to accelerating the computation of scoring matrices is to employ vectorized computing for independent cells. This method has become more practical with the advent of SIMD computing, which supports spatial parallelism by executing multiple data operations simultaneously using a single instruction. Prior to this advancement, Alpern and Bowen [4] recommended using microparallelism for protein matching. This approach is akin to SIMD technology in that it allows for the simultaneous alignment of a query protein sequence with multiple reference protein sequences, utilizing the same control structure at the instruction level and enabling parallel sequence-to-bank alignment. In a different approach, Wozniak [5] rearranged each row of the initial scoring matrix uniquely, aligning diagonal cells into columns, thereby facilitating the parallel acceleration of sequence-to-sequence operations through a SIMD-like Visual Instruction Set technology. Conversely, Rognes et al. [6] transformed the SIMD method from a diagonal to a parallel configuration relative to the query sequence. Their algorithm leverages MultiMedia eXtensions with a 64-bit single instruction and Streaming SIMD Extensions (SSE) with a 128-bit instruction. Subsequent algorithms have integrated advanced vector extensions (AVX) techniques, such as libssa [7], and novel 512-bit SIMD instruction sets (AVX-512), exemplified by XSW [8]. Difference recurrence relation In the SIMD technique, registers have a fixed length and can hold multiple types of data. By utilizing smaller data types, it becomes possible to perform computations on a larger number of values simultaneously. Initially, Myers [9] employed a relocatable DP matrix that includes both horizontal and vertical deltas in the Fast Bit-Vector Algorithm for Approximate String Matching. This algorithm is used for approximate string matching. Shortly thereafter, BitPAl [10] utilized a similar technique for sequence alignment, integrating a more comprehensive scoring methodology that relies on three distinct values: match, mismatch, and gap. BitPAl demonstrates the potential for further optimization using the SIMD approach. Suzuki and Kasahara [11] integrated and optimized incremental relations and SIMD techniques in dynamic banded DP (adaptive banded DP), referring to the former as difference. This method employs the SIMD technique to calculate difference recurrence relations (DRR) in both horizontal and vertical directions for specific cells on the antidiagonal. By reducing the stored values in the standard DP matrix from 32-bit to 8-bit, the number of cells computed simultaneously increases by a factor of 4. Minimap2 (RRID:SCR_018550) [12] extends the DRR to a two-piece affine gap cost-model and, to implement an SSE technology more efficiently on this basis, it transforms row-column coordinates into diagonal-antidiagonal coordinates. Striped SIMD Wozniak’s method [5] demonstrates that loading values on the reverse diagonal of the DP matrix requires an additional complex process due to the discontinuous nature of these values during storage. Rognes et al. [6] found that vectorizing cells along the query sequence results in faster processing. However, it still necessitates non-vectorized computations for resolving dependencies. Subsequently, Farrar [13] proposed a technique called “striping”, wherein cells are reorganized along the query sequence into multiple strips. This method resolves dependency relationships by incorporating several correction cycles in the direction of the dependency. The number of correction loops is determined by the length of the gap. This approach has been employed in numerous subsequent algorithms, such as SWPS3 [14], CUDASW++2.0 (RRID:SCR_008862) [15], and others. Some mappers also employ striped SIMD techniques, such as BWA-MEM (RRID:SCR_022192) [16], which uses this technique to realign paired-end reads that may have been unmapped for various reasons. Recently, bsalign [17] optimized the correction method in the F direction through an active and proactive “breakdown” approach. Multithreading An alternative method to accelerate the computation process is to employ multiple threads for parallel calculation of the non-dependent sections of the sequence alignment. This approach is efficient when the benefit of speeding up these threads outweighs the cost of additional overhead. The multithreaded technique can significantly enhance inter-sequence alignments, particularly when numerous alignments are required. Rognes’ SWIPE software (RRID:SCR_012771) [18] utilizes this inter-sequence parallel approach for the Smith–Waterman algorithm, achieving outstanding results for local alignments. The Parasail library (RRID:SCR_021805) [19] extends the range of alignment by developing an independent C library that includes global, semi-global, and local alignment. The BGSA [20] algorithm employs data-level parallelism using multiple processing units, such as CPUs and Xeon Phis, and applies them in bit-parallel global sequence-alignments. Additionally, Jacek Blazewicz et al. [21] enhanced the progressive multiple sequence alignment method using the inter-sequence parallel approach. This involves dividing the task matrix into smaller windows, each processed on a single GPU, where individual threads align pairs of sequences within each window. In contrast, the intra-sequence thread-parallelism technique was initially utilized by Edmiston et al. [22] and Liu et al. [23], who applied multithreading to non-dependent cells located on the anti-diagonal in the scoring matrix. Rahn et al. [24] introduced the Generalised Wavefront Model to group certain independent blocks in the score matrix, such as blocks near the anti-diagonal, based on the instruction set type. Subsequently, the blocks within each group were computed vertically using the SIMD instruction set. POA In 2002, the field of multiple sequence alignment (MSA) research saw the introduction of a novel approach called partial order alignment (POA) [25], which employed graph-based techniques. POA uses directed acyclic graphs to establish connections between sequences. Unlike in pairwise sequence alignment (PSA), the source of a node in POA is not restricted to a single node during alignment. Nodes are merged based on their alignment scores, and the final alignment result is derived from the fused graph. Similarly, the SIMD approach can be integrated into the POA algorithm. Vaser et al. developed the SPOA [26] algorithm, which uses SIMD vectors to parallelize computations along the query sequence. It performs parallel computations that are both perpendicular to the query sequence and along the diagonal line. However, due to data dependency, horizontal computations are performed linearly rather than using SIMD operations for efficiency. Additionally, the abPOA method developed by Yan Gao et al. [27] integrates the adaptive banded DP approach into the SPOA algorithm. This incorporation effectively reduces the computational memory and time required for computation. This paper presents an accelerated algorithm for the global alignment of pairwise and multiple sequences. The algorithm integrates four methods: the difference method, the stripe method, the SIMD instruction set, and multithreading. These integrations result in significant improvements in the speed of both pairwise and multiple sequence alignment, particularly for long sequences. Materials and methods Global alignment In contrast to local alignment, which seeks to identify local overlaps, global alignment evaluates entire sequences to determine the optimal alignment. The Needleman–Wunsch–Gotoh algorithm is employed for global alignment scoring: Initial: Extension: In this context, M (i, j) represents the optimal score for the coordinates (i, j) in the scoring matrix, whereas E (i, j) and F (i, j) represent the scores in the vertical and horizontal directions, respectively. The variable e denotes the penalty score for extending a gap, while the variable o represents the penalty score for opening a gap. The variable D stands for the match/mismatch score. This algorithm utilizes an affine penalty model. A brief overview of the POA The POA method converts the sequence into a DAG, where each base in the sequence is represented as a node in the graph. Directed edges, indicating dependencies between nodes, represent their connections (Figure 1A). Subsequently, the nodes are arranged in a topological order, resulting in a linear-like structure. Following this arrangement, a computation resembling the pairwise sequence alignment model occurs, albeit with the distinction that the score of each cell is not exclusively derived from three sources (Figure 1B). Upon completion of the score matrix calculation, nodes with matching sequences are merged to form a new graph (Figure 1C), which then undergoes iterative calculations for subsequent sequences. (A) POA graph and sequences of the alignment. The bold path indicates that multiple sequences have passed through. (B) The scoring matrix. The POA graph is topologically sorted into a linear-like structure and aligned with seqB. The scores of cells (A, A) are derived from the maximum values in five directions. (C) The new POA graph with the seqB sequence is in blue. Difference method The difference method is implemented as an alternative to the classic Needleman–Wunsch–Gotoh alignment algorithm, facilitating parallel computation of substantial data volumes through the utilization of registers in the SIMD instruction set, capable of accommodating varying bit sizes. This approach employs ΔH and ΔV (Figure 2) to denote the difference value (D-value) between adjacent cells in horizontal and vertical orientations. Typically, substantial enhancements in parallel efficiency can be achieved by leveraging the minimal specification of 8 bits in the registers. The difference method of pairwise sequence alignment. ΔH, ΔV respectively represent the difference between adjacent cells in the horizontal and vertical directions. E is the difference between the score of B obtained in the vertical direction and the score of A, and F is the difference between the score of B obtained in the horizontal direction and the score of A. The variable q is the matching/mismatch score. PSA initially calculates the maximum D-value S between the current cell and the top left cell. It next calculates the horizontal D-value ΔH and vertical D-value ΔV of the current cell individually: MSA directly calculates the maximum horizontal D-value ΔH of the current cell, and then calculates the ΔV x between the current cell and each previous node: The computational approaches for PSA and MSA exhibit slight variations. The PSA method computes the maximum D-value between the upper left cell and the current cell, and subsequently subtracts ΔV (i, j−1) to obtain ΔH (i, j). Conversely, the MSA method capitalizes on the uniqueness of ΔH (i, j) to determine its maximum value (Figure 3). The difference method of POA multiple sequence alignment. The variables ΔH 1 and ΔH 2 represent the differences between neighboring cells in the horizontal direction of the two front nodes in the POA graph. Similarly, the variables ΔV 1 and ΔV 2 represent the differences between adjacent cells in the vertical direction of the two front nodes in the POA graph. Due to the existence of two preceding nodes, there will be a total of two instances of E and F. Because q is only related to whether the base matches, the values of q 1 and q 2 are equal. Stripe method Farrar [9] recommends employing a stripe method to enhance the implementation of in-sequence parallelism, resulting in significant improvements in parallel performance through the utilization of the SIMD instruction set. This method involves reorganizing the originally sequential computation. The length of each stripe corresponds to the processing capacity of the SIMD register, with any remaining space in the register filled with dummy symbols having no impact on the outcome. Farrar’s approach utilizes the Lazy-F method in parallel computing to eliminate data interdependencies among F vectors, whereas the TSTA algorithm employs the Active-F method. The former necessitates multiple updates to the value of each register after the initial loop until the ultimate value is achieved, while the latter updates the value of the last register obtained after the initial loop and subsequently executes another loop to attain the ultimate value (Figure 4). Stripe method. Original order: The original sequence, length = register size × number of stripes. Initial loop: Rearranges the original sequence by grouping every four cells in a striped pattern, resulting in a non-sequential arrangement. Then, it proceeds with the initial loop computation. Due to the correctness of the first value in the first register and the consecutive nature of the calculations, the first value in each register is correct. Update: Updates the value in the last register (excluding the first value) acquired from the initial loop. Each score is derived from three sources (multiple sequence alignment can also be generally categorized into three types of sources). The vertical and match/mismatch scores are already known, and the first value of the register is confirmed to be precise. Thus, in this stage, it solely assesses if the horizontal score has been breached. If it has been breached, it will be updated; otherwise, it will remain unaltered. Final loop: Performs a second loop based on the updated values to obtain the final correct value. Through the integration of the difference approach with the stripe method, it becomes feasible to extend the lengths of individual stripes, such as SSE (16), AVX (32), and AVX512 (64). This strategy can be employed in both PSA and MSA. Thread-level ladder parallelism Among the in-sequence parallelism methods, calculations utilizing an anti-diagonal layout were among the earliest to be conceived and are frequently utilized. While this method is not compatible with the SIMD instruction set parallelism, employing threads to compute independent units on the anti-diagonal remains a viable option. However, allocating computational resources to invoke threads constitutes a significant portion of the total runtime. Therefore, employing threads solely to compute each cell on the anti-diagonal does not yield favorable results. Consequently, the TSTA algorithm divides the entire scoring matrix into multiple blocks of equal length and width along the anti-diagonal. These blocks are then computed in parallel threads to substantially minimize the overhead associated with invoking threads. Within each block, a parallel technique is employed, combining the difference method and the stripe method to enhance parallel efficiency. The formula utilized in this method is L = S × D, where L represents the width of the block in bits, S represents the size of the register (16/32/64 bits), and D is the number of stripes. Both the values of S and D influence the speed of the calculation, though the value of S is contingent upon the machine’s level of support. This research entails the incorporation of all blocks along each anti-diagonal into the thread pool as tasks. Subsequently, the calling threads within the thread pool engage in competition for the independent completion of these tasks individually (Figure 5). It is ensured that the block tasks on the subsequent anti-diagonal are not incorporated into the thread pool until all blocks on the current anti-diagonal have been computed, accounting for their dependencies. Thread parallel method. First, it partitions the entire matrix into multiple anti-diagonal lines, with each line consisting of independent blocks of equal size. Subsequently, it allocates all blocks situated on each diagonal to the task pool of the thread pool, where the thread concurrently computes the score of these blocks. The block in the picture has a width of 16 bases. To minimize memory usage, each thread in PSA only requests a memory block of char type that is two units long (16 × 2, as illustrated in Figure 4) to store the ΔH values. This memory block is released once the block has been processed. The algorithm utilizes a single memory to store and update the true value of the vertical total length of the scoring matrix, which is also employed to determine the maximum value of the matrix and the necessary ΔV value for each thread calculation. Additionally, a dedicated memory is utilized to store and update the ΔH value of the horizontal total length of the scoring matrix, with each thread accessing and modifying this value from memory. These two memories alternate as dependency rows and computation rows. Moreover, the last true value of each row and the ΔH value of the last row are recorded to calculate the related blocks of the next anti-diagonal line. In the context of MSA, nodes that do not span block boundaries necessitate a memory allocation equivalent to the block length to store the ΔH value. Conversely, nodes that cross block boundaries require a memory allocation equal to the length of the sequence to store ΔH values. Result The test was divided into two groups based on the presence of backtracking regarding PSA. Within the context of backtracking, TSTA was evaluated alongside bsalign [13] and parasail. Conversely, the group without backtracking compared TSTA with align_bench_wave [22] and parasail. In addition, TSTA was compared to SPOA, abPOA, and bsalign for MSA. Across all evaluations, we employed the affine gap model, featuring a match score of 2, a mismatch score of −3, and gap extension and gap open penalties of −2 and −4, respectively. The align_bench_wave algorithm utilized its inherent scoring system. All experiments, except for abPOA, were conducted with the band disabled and set to global alignment. The experiments were conducted on a computer equipped with 2.10 GHz Intel Xeon Gold 6230R CPUs, featuring 52 cores and 376 GB of RAM. We evaluated the performance of our algorithm, SPOA, and bsalign using the SSE4.2 instruction set. Additionally, we assessed the performance of abPOA and parasail using the AVX2 instruction set and align_bench_wave using the AVX-512 instruction set. Notably, the SPOA software is installed using Conda (RRID:SCR_018317), exhibiting a faster alignment speed than the AVX-optimized version included in the git repository. Furthermore, the parasail library employs a 32-bit integer data type to mitigate the risk of computational overflow. We utilized 30 threads for align_bench_wave, parasail, and our algorithm. In the aforementioned algorithms, we assessed the time expended on both real and simulated datasets. The real datasets comprised three sets of sequences with average lengths of 1k bps (accession number ERR12439694), 10k bps (accession numbers ERR11890836 and SRR10673221), and 50k bps (accession numbers SRR27371247 and SRR27371637), respectively. The datasets in PSA were categorized into 637, 8,600, and 17 alignments. Meanwhile, the authentic data in MSA were categorized into groups of five sequences (5×) and ten sequences (10×). Within the 5× groups, there were 254, 3,399, and 7 group alignments, whereas in the 10× groups, there were 127, 1,699, and 3 group alignments. The data source can be viewed in the DATA AVAILABILITY section [28]. For the simulated dataset, we randomly selected 100 sequences of 200k bases’ regions from GRCh38. Subsequently, we employed PbSim2 (RRID:SCR_002512) [29] to simulate query sequences for each reference region. One query sequence was chosen from each set to serve as input sequence along with its respective reference sequence for PSA. Furthermore, subsets of five and ten sequences were selected from the query sequences to form two sets of input sequence groups for MSA. Due to the decreased efficiency of MSA, particularly with larger sequences (>100k bases), varied sequence lengths were utilized in testing. Additionally, the maximum memory limit of the computer restricts the sequence length that can be processed, whereas PSA is more flexible in this regard. In the context of PSA, sequence lengths were set at 10k, 20k, 50k, 100k, and 200k. Moreover, in the context of MSA, the number of sequences was set at 5 and 10, with lengths of 5K, 10K, 20K, and 50K. Evaluating time with different numbers of threads and stripes The number of threads is denoted by T, while the number of stripes in the striping method is represented by B. We assessed the optimal outcomes for various combinations of T and B values. Figure 6 illustrates the speed for several combinations at a rate of pairwise sequence alignment (200k bases) and multiple sequence alignment (10× 150k bases). The peak speed was achieved when B was set to 30 and T was set to 30. Time spent on the alignment of two 200k bases sequences (A) and ten 50k bases sequences (B) in the TSTA algorithm for different block sizes and different numbers of threads. It is worth noting that Figure 6 distinctly illustrates a sudden increase in time when B equals 5 and T equals 30. At this juncture, there is a higher number of threads and smaller blocks, resulting in frequent thread switching. Additionally, the intricate computational preparation of each block counteracts the speedup performance. Furthermore, it is noteworthy that the reduction in time spent is not directly proportional to the increase in block size or the number of threads. While employing a larger block with more threads may marginally expedite execution time, the improvement in speed is often only a matter of seconds or milliseconds. Consequently, utilizing a larger block or more threads results in an even lower acceleration ratio. In Figure 6, the execution time for a B∕T ratio of 30/30 is only marginally shorter than the combined times for 30/20 and 20/30. Consequently, the values of parameters B and T were not escalated continuously. In our alignment approach, both B and T were set to 30. Evaluating time under real data The PSA and MSA were assessed on real and simulated datasets, respectively, as delineated in Tables 1 and 2. In handling real datasets, TSTA demonstrated several advantages across all three datasets. In the “no backtracking” mode, the TSTA algorithm emerged as the fastest, showcasing performance that was 1.47, 2.68, and 3.08 times superior to seqan_wave, and 3.38, 3.08, and 5.29 times greater than parasail, respectively. When operating in “backtracking” mode, the TSTA algorithm proved to be the second most efficient, closely approaching the performance of the bsalign algorithm with a 50k bases dataset. Furthermore, TSTA demonstrated reduced CPU time and decreased thread utilization in the 1k bases dataset, while manifesting elevated values in the other two datasets. In multiple sequence alignment, TSTA showcased the highest speed in the 50k bases dataset, surpassing the SPOA method by 4.22 and 5.02 times and bsalign by 1.68 and 2.61 times in the two datasets, respectively. However, in the 10k bases dataset, its speed was slower than with bsalign, with a trade-off observed with abPOA, which outperformed SPOA. Moreover, the TSTA algorithm exhibited the lowest processing speed among the 1k bases dataset. Overall, in the 50k bases dataset, the TSTA method manifested the highest speed. Table 1Time (ms) comparison under the pairwise sequence alignment algorithms. a PSA-time (ms)RealSimulated Length of sequence 1k 10k 50k 10k 20k 50k 100k 200k No-tracebackTSTATSTA-CPUseqan_waveseqan_wave-CPUparasailparasail-CPU44 15 65528149101741871993,0012281,4922042,22863015,1371,0816,627281791913,2112841,760556582906,0514094,6671762,23558814,5941,4526,6692796,3531,18432,139errorerror97824,4763,69685,056errorerror Traceback TSTATSTA-CPUbsalignparasailparasail-CPU49 23 11156351 2387001475806,1542,19115,2821,96210,57616,054 248716867425,8844802,6223161,9687,3781,84615,1171,92512,03116,316 6,00159,8487,659errorerror 24,385254,24951,147errorerror a TSTA and parasail were tested separately in two modes with and without backtracking, respectively. “error” indicates that the method could not complete the alignment on the dataset due to memory overflow. Time (ms) comparison under the pairwise sequence alignment algorithms. a a TSTA and parasail were tested separately in two modes with and without backtracking, respectively. “error” indicates that the method could not complete the alignment on the dataset due to memory overflow. Table 2Time (ms) comparison under multiple sequence alignment algorithms. a MSA-time (ms)RealSimulated Length of sequence1k10k50k5k10k20k50k Number of sequences5×10× 5× 10× 5× 10× 5× 10× 5× 10× 5× 10× 5× 10× TSTA881851,1653,94314,04436,4384439679022,1922,2565,5508,75119,424 TSTA-CPU 1273807,77234,578205,142571,6431,8025,0296,53519,63524,47669,349130,293320,236 SPOA57782,1776,43659,404183,2193117011,8554,7227,60619,46850,003128,677 abPOA49661,5993,214errorerror1692698201,7264,4786,305errorerror bsalign611291,0253,88323,64395,2872497368162,6402,84810,39017,74461,879 a Time (ms) comparison under the MSA algorithm. Only TSTA uses threads, so only TSTA records CPU time. Time (ms) comparison under multiple sequence alignment algorithms. a a Time (ms) comparison under the MSA algorithm. Only TSTA uses threads, so only TSTA records CPU time. Evaluating time at different lengths in a simulated dataset We assessed the performance of all algorithms using five categories of sequence lengths for PSA and four categories of sequence lengths for MSA. In PSA, under the “no backtracking” mode, TSTA demonstrated superior real-time and CPU performance compared to other algorithms across all five datasets. In the “backtracking” mode, TSTA ranked second only to bsalign when the sequence length was equal to or less than 20k bases. However, TSTA emerged as the fastest when the sequence length equaled or exceeded 50k bases, while parasail failed to perform the matching task when the sequence length reached or exceeded 100k bases. The advantages of TSTA became more apparent with longer sequences. At a sequence length of 100k bases, TSTA was 1.27 times faster than bsalign, and at a length of 200k bases, it accelerated by 2.09 times compared to bsalign. Regarding MSA, TSTA performed at an intermediate level when the sequence length was less than or equal to 10k bases. Nevertheless, TSTA emerged as the fastest when the sequence length equaled or exceeded 20k bases, consistent with the trend observed in PSA. While abPOA encountered limitations in processing sequence lengths of 50k bases, it failed to exhibit a favorable speed trend across sequences ranging from short to lengthy. To test our algorithm’s ability to handle longer sequences in multiple sequence alignments, we performed an MSA test with 60 sequences at 100k bases each (Table 3). Notably, there was a large disparity between the first five alignments and the last five in Table 3. As they were taken from different parts of two groups from the previous pairwise alignments in the 100k bases category, those selected from the same group had similar time expenditures, whereas those from different groups differed greatly due to variations in the construction of the POA graphs. Table 3Time (min) comparison under the 60× 100k bases alignment algorithms.MSA-time (min) Real41444342402425242525 CPU572577583581568602615608611617 Time (min) comparison under the 60× 100k bases alignment algorithms. More detailed evaluation time With 30 threads, a more detailed breakdown of the time spent is shown in Tables 4 and 5. Firstly, all times except I/O increased in direct proportion to the number or length of sequences. Additionally, in terms of composition, communication and I/O times made up a very small fraction of the total CPU time, with most of the CPU time being devoted to computation. Notably, the communication time we calculated is the sum of the time spent by all threads when passing through thread locks. Table 4Detailed time (ms) comparison under the pairwise sequence alignment algorithms.PSA-time (ms) Length of sequence 10k 20k 50k 100k 200k Real 248 480 1,846 6,001 24,385 CPU 716 2,622 15,11759,848254,249 Communication 0.25 1.022 5.922.766 74.92 I/O38.70143.002102.97456.109 74.079 Detailed time (ms) comparison under the pairwise sequence alignment algorithms. Table 5Detailed time (ms) comparison under the multiple sequence alignment algorithms.MSA-time (ms) Length of sequence5k10k20k50k Number of sequences5×10× 5× 10× 5× 10× 5× 10× Real 4439679022,1922,2565,5508,75119,424 CPU 1,8025,0296,53519,63524,47669,349130,293320,236 Communication 0.3780.9691.5445.148.95423.04438.88100.501 I/O 39.78428.59710.4321.381.9233.00640.9515.935 Detailed time (ms) comparison under the multiple sequence alignment algorithms. Contribution of the SIMD and thread We analyzed whether threading accelerates the program. Table 6 clearly illustrates the time spent under different methods, with the subject being multiple sequence alignments at 5× 20k bases each. We found that using the SIMD technology alone was 2.64 times faster than not using any acceleration techniques. As the number of threads increased from 5 to 30, the speedup rised from 6.69 times to 9.1 times. Hence, threading provided a significant acceleration, but the effect of additional threads diminished considerably. Table 6Time consumption under different acceleration conditions.5× 20k basesMode Time (ms) MultiplesNo acceleration 20,529.6 1.0Only SIMD 7,776 2.64 TSTAThreads51020303,0682,4912,3322,2566.69 8.24 8.89.1 Time consumption under different acceleration conditions. Comparison of memory We conducted a comparative analysis of execution memory costs across various software applications, as presented in Tables 7 and 8. Table 7 illustrates that the backtracking phase incurs the highest level of memory consumption. Although we did not explicitly optimize memory usage, we could conserve it as much as possible. However, our technique led to higher memory consumption compared to bsalign. For example, as shown in Table 8, although TSTA consumes more memory than bsalign, it outperforms SPOA and abPOA in all categories. Table 7Memory (Mb) comparison under the pairwise sequence alignment algorithms.PSA-memory (Mb) Length of sequence 1k10k20k50k100k200k No-tracebackTSTAseqan_waveparasail <1515<1630<1727<1830110error222error Traceback TSTAbsalignparasail 43192751863921,0997321,4706,8064,5409,11326,82718,181error108,57172,291error Memory (Mb) comparison under the pairwise sequence alignment algorithms. Table 8Memory (Mb) comparison under the multiple sequence alignment algorithms.MSA-memory (Mb) Length of sequence1k5k10k20k50k Number of sequences5×10× 5× 10× 5× 10× 5× 10× 5× 10× TSTA 12181271614756051,8472,32411,28314,255 SPOA 22302352941,8142,2547,1398,65044,37853,764 abPOA 20333784752,6563,24511,92514,432errorerror bsalign711871243134021,2882,1318,58411,326 Memory (Mb) comparison under the multiple sequence alignment algorithms. Limitations To further validate the effectiveness of TSTA, we conducted tests using several larger datasets. For a dataset containing sequences of 10,000 by 20k bases, TSTA required 890 min, whereas bsalign and spoa took 15 and 2,392 min, respectively. With a dataset comprising 200 sequences of 100k bases each, TSTA completed the processing in 48 min, bsalign took 98 min, and spoa was unable to complete the alignment. In a smaller dataset of 50 sequences, each consisting of 200 bases, TSTA processed the data within 12 min, bsalign required 20 min, and spoa once again failed to complete the task. Additionally, we attempted to test sequences with lengths of 100k and 200k bases, but due to memory constraints in our testing environment, all three algorithms were unable to proceed. From these results, it is evident that TSTA performs well in scenarios involving longer sequences (>50k bases) and a moderate or smaller number of sequences. However, when dealing with a larger number of shorter sequences, TSTA’s efficiency falls short of expectations, although it still surpasses the performance of spoa. Discussion and conclusions Employing threads to expedite sequence alignment holds promise for longer sequences but may not be advantageous for shorter ones. In the latter cases, both multithreading and striped SIMD data structures become redundant. Optimization strategies for alignment must strike a balance between speedup and overhead. Furthermore, employing threads for certain intricately designed algorithms may not yield substantial speedups. For instance, in the case of the bsalign algorithm, which also employs the difference and striping methods, reconfiguring it according to the design of our algorithm may disrupt memory accesses and result in unchanged or even inferior outcomes. However, it is noteworthy that a more refined multithreaded design solution could potentially alter this scenario. Additionally, during the backtracking phase, a lot of memory is used, and accessing the data created during this phase takes a significant amount of time. Thus, optimizing the backtracking stage is critical for future research. Our findings demonstrate TSTA’s efficacy in pairwise sequence alignment and multiple sequence alignment, particularly with long reads, showcasing considerable speed enhancements compared to existing tools. We anticipate that TSTA will offer enhanced value and play a pivotal role in bioinformatics. Availability of source code and requirements Project name: TSTA Project name: TSTA Project home page: https://github.com/bxskdh/TSTA Project home page: https://github.com/bxskdh/TSTA Operating system(s): Platform independent Operating system(s): Platform independent Programming language: C Programming language: C License: MIT License: MIT Biotools: biotools:tsta Biotools: biotools:tsta RRID:SCR_025750. RRID:SCR_025750. Acknowledgements We would like to thank Mr. Deng for his help in testing the algorithm and reviewing the manuscript. Funding Statement This work was supported by the National Key Research and Development Program of China (2022YFC3400300 to JR) and the Innovation Program of the Chinese Academy of Agricultural Sciences. Data availability All supporting datasets are available in Figshare [28]. Abbreviations AVX, advanced vector extensions; DP, dynamic programming; DRR, difference recurrence relations; MSA, multiple sequence alignment; POA, partial order alignment; PSA, pairwise sequence alignment; SIMD, Single Instruction Multiple Data; SSE, Streaming SIMD Extensions. Declarations Ethics approval and consent to participate Not applicable. Competing interests The authors declare that they have no competing interests. Authors’ contributions PZ, conceptualization; PZ, project administration; PZ and WD, software; PZ, data collection, processing, and application; WD, project coordination; PZ, manuscript writing and figure generation; JL, manuscript review. Funding This work was supported by the National Key Research and Development Program of China (2022YFC3400300 to JR) and the Innovation Program of the Chinese Academy of Agricultural Sciences. References Reviewer name and names of any other individual's who aided in reviewerBaoxing SongDo you understand and agree to our policy of having open and named reviews, and having your review included with the published manuscript. (If no, please inform the editor that you cannot review this manuscript.)YesIs the language of sufficient quality?YesPlease add additional comments on language quality to clarify if neededIs there a clear statement of need explaining what problems the software is designed to solve and who the target audience is? YesAdditional CommentsIs the source code available, and has an appropriate Open Source Initiative license (https://opensource.org/licenses) been assigned to the code?YesAdditional CommentsAs Open Source Software are there guidelines on how to contribute, report issues or seek support on the code?YesAdditional CommentsIs the code executable?YesAdditional CommentsIs installation/deployment sufficiently outlined in the paper and documentation, and does it proceed as outlined?YesAdditional CommentsIs the documentation provided clear and user friendly?YesAdditional CommentsIs there enough clear information in the documentation to install, run and test this tool, including information on where to seek help if required?Additional CommentsIs there a clearly-stated list of dependencies, and is the core functionality of the software documented to a satisfactory level?YesAdditional CommentsHave any claims of performance been sufficiently tested and compared to other commonly-used packages? YesAdditional CommentsIs test data available, either included with the submission or openly available via cited third party sources (e.g. accession numbers, data DOIs)?Additional CommentsAre there (ideally real world) examples demonstrating use of the software? YesAdditional CommentsIs automated testing used or are there manual steps described so that the functionality of the software can be verified?Additional CommentsAny Additional Overall Comments to the AuthorZong et al. implemented a TSTA package that integrated the difference method, the stripe method, SIMD, and multiple threading approaches to perform efficient sequence alignments. The TSTA toolkit could conduct pairwise and multiple sequence alignments. The memory cost of TSTA is comparable with the most efficient one. Overall, TSTA is a good package, and the manuscript is well-written. While I have a few suggestions: 1) The minimap2 should be mentioned in the section on "difference recurrence relation." It has a much broader range of users and implemented an algorithm that is slightly different from the one by Suzuki, etc. 2) The striped SIMD is also implemented in reads mappers, such as BWA. 3) Page 14, line 215 "1k bps", line 227 "1000 kbps", line 230 and table1 "100k". They should be consistent. 4) In Table 4, I am not sure I understood the second and third lines correctly. Please clarify. 5) I tried to compile TSTA from the source code. To compile the package, I had to copy 'seqio.h' into the 'msa' and 'psa' folders. Please fix it.RecommendationMinor Revisions Reviewer name and names of any other individual's who aided in reviewerYuansheng LiuDo you understand and agree to our policy of having open and named reviews, and having your review included with the published manuscript. (If no, please inform the editor that you cannot review this manuscript.)YesIs the language of sufficient quality?YesPlease add additional comments on language quality to clarify if neededIs there a clear statement of need explaining what problems the software is designed to solve and who the target audience is? YesAdditional CommentsIs the source code available, and has an appropriate Open Source Initiative license (https://opensource.org/licenses) been assigned to the code?YesAdditional CommentsAs Open Source Software are there guidelines on how to contribute, report issues or seek support on the code?YesAdditional CommentsIs the code executable?YesAdditional CommentsI do not test.Is installation/deployment sufficiently outlined in the paper and documentation, and does it proceed as outlined?YesAdditional CommentsIs the documentation provided clear and user friendly?YesAdditional CommentsIs there enough clear information in the documentation to install, run and test this tool, including information on where to seek help if required?YesAdditional CommentsIs there a clearly-stated list of dependencies, and is the core functionality of the software documented to a satisfactory level?YesAdditional CommentsHave any claims of performance been sufficiently tested and compared to other commonly-used packages? YesAdditional CommentsIs test data available, either included with the submission or openly available via cited third party sources (e.g. accession numbers, data DOIs)?Additional CommentsAre there (ideally real world) examples demonstrating use of the software? NoAdditional CommentsIs automated testing used or are there manual steps described so that the functionality of the software can be verified?Additional CommentsAny Additional Overall Comments to the AuthorThe article explores strategies for accelerating sequence alignment using multithreading and SIMD (Single Instruction, Multiple Data) techniques, and introduces a new algorithm called TSTA. The paper provides a detailed description of TSTA's performance in pairwise sequence alignment (PSA) and multiple sequence alignment (MSA), and compares it with various existing alignment algorithms. Experimental results indicate that TSTA demonstrates significant speed advantages, particularly when handling long sequences and in the no-backtracking mode. However, the experiments on MSA are limited by the experimental environment, which does not fully address the needs of current sequencing technologies concerning long reads and depth. Specifically, the low number of sequences in MSA does not meet the requirements for downstream genomic analysis applications. While the algorithm is highly innovative, its performance on short sequences and during the backtracking phase still requires optimization. 1. In line 7, the TSTA algorithm utilizes vector-level and thread-level parallelism to accelerate pairwise and multiple sequence alignment. Why are there no experiments designed specifically to evaluate the global alignment performance of TSTA with vector-level parallelism? Or are there any other experimental designs that demonstrate the improved performance of TSTA when vector-level parallelism is employed? 2. In line 149, is the Active-F method used by the TSTA algorithm contributing to the excessive memory usage and access time overhead observed during the iterative process of PSA? Are there better optimization strategies from this perspective? If not, why does TSTA incur higher time costs in traceback as shown in Table 1? Why does bsalign result in lower time consumption? 3. Can you provide the time breakdown for each part of the parallel computation in TSTA for PSA (including at least CPU computation overhead, communication overhead, and I/O overhead) to clarify if there will be significant communication overhead issues with larger datasets and more threads? 4. Table 2 shows that both real and simulated datasets have issues with insufficient depth and short reads. In real MSA processes, it is common to encounter comparisons with depth over 60X and lengths exceeding 100 kbps for long reads. The results under the current experimental conditions seem to perform poorly for such data scenarios. Can you address this? 5. Gene data often includes repetitive regions that affect the accuracy of alignment algorithms. Can you design experiments to verify how TSTA performs in aligning long repetitive regions? Specifically, how accurately does TSTA align sequences in such regions compared to other methods? 6. Besides repetitive regions, sequencing errors produced by ONT R10 chips can also impact alignment accuracy. Alignment algorithms used in genome correction often struggle to detect such errors. How does TSTA handle such issues during MSA? Can the algorithm be designed to address these sequencing errors more effectively?RecommendationMajor Revisions Indicate in the comments box below whether you are happy with the changes made or if the manuscript is unacceptable.Comments on revised manuscriptAfter thoroughly reviewing the revised manuscript and testing the TSTA tool, I cannot endorse the manuscript for publication in its current form. I encourage the authors to address the following issues thoroughly and consider re-submitting after significant improvements. Efficiency Concerns: In the context of multiple sequence alignment (MSA), I find that TSTA does not demonstrate a significant advantage in terms of efficiency. I conducted a test with approximately 2G of homologous diploid reads (not too large data), and the tool has been running for around 29 hours. Despite this extensive runtime, the process remains incomplete. This is far from the efficiency one would expect from a tool designed for large-scale sequence alignment. Functionality Issues: There are still unresolved issues with the tool's functionality. The -f parameter does not appear to work as intended, and there are also problems with the -o parameter. Such issues need to be addressed to ensure the tool's reliability and usability. Indicate in the comments box below whether you are happy with the changes made or if the manuscript is unacceptable.Comments on revised manuscriptThe authors themselves acknowledged that their tool performs well only for moderate or small datasets, which restricts its utility in broader applications that require large-scale sequence analysis. For a journal like GigaByte, which focuses on scalable and impactful bioinformatics tools, this limitation may hinder its relevance for publication. Editor’s AssessmentThe article presents strategies for accelerating sequence alignment using multithreading and SIMD (Single Instruction, Multiple Data) techniques, and introduces a new algorithm called TSTA (Thread and SIMD-Based Trapezoidal Pairwise/Multiple Sequence-Alignment). The Technical Release write-up presenting a detailed description of TSTA's performance in pairwise sequence alignment (PSA) and multiple sequence alignment (MSA), and compares it with various existing alignment algorithms. Demonstrating the performance gains achieved by vectorized SIMD technology and the application of threading. Testing and debugging a few errors, and adding some more background detail, demonstrating it can achieve faster comparison speed. Demonstrating TSTA's efficacy in pairwise sequence alignment and multiple sequence alignment, particularly with long reads, and showcasing considerable speed enhancements compared to existing tools.Editor’s AssessmentThe article presents strategies for accelerating sequence alignment using multithreading and SIMD (Single Instruction, Multiple Data) techniques, and introduces a new algorithm called TSTA (Thread and SIMD-Based Trapezoidal Pairwise/Multiple Sequence-Alignment). The Technical Release write-up presenting a detailed description of TSTA's performance in pairwise sequence alignment (PSA) and multiple sequence alignment (MSA), and compares it with various existing alignment algorithms. Demonstrating the performance gains achieved by vectorized SIMD technology and the application of threading. Testing and debugging a few errors, and adding some more background detail, demonstrating it can achieve faster comparison speed. Demonstrating TSTA's efficacy in pairwise sequence alignment and multiple sequence alignment, particularly with long reads, and showcasing considerable speed enhancements compared to existing tools. Data Availability Statement All supporting datasets are available in Figshare [28].