Introduction

This paper is devoted to the development of an algorithm for preventing chromosomal translocations and inversions. Chromosomal translocations and inversions are complex structural changes in genetic materials that occur as a result of disruptions in the organization of chromosomes. Translocations involve moving a part of a chromosome to another, causing genetic sequences to be interrupted and reconnected, while inversions occur when a chromosome fragment rotates around its axis, changing the order of genes and other genetic elements. These structural variations can occur as a result of various errors during cell division. Incorrect joining or rotation of chromosome parts can lead to important changes in genetic information, which is often associated with the development of various genetic diseases and developmental disorders [1].

The main reasons why it is important to avoid chromosomal translocations and inversions: 1. A translocation between chromosomes 21 and 14 can lead to "familial" Down syndrome, where one of the parents may be a carrier of the translocation. This, in turn, can affect the likelihood of having a child with Down syndrome. 2. Gametes carrying defective chromosomes with inversion often develop into non-viable or miscarried organisms in the early stages of embryogenesis.

3. Robertson translocations can cause differences in the number of chromosomes between closely related species, which affects their fertility and genetic stability. 4. If gametes with an inverted chromosome develop into organisms, 50% of the gametes of these organisms may not be viable. However, the other 50% may be viable and maintain the mutation in the population.

Thus, the diagnosis and prediction of chromosomal inversions and translocations are critical in genetic research and medical practice. Detection of these changes contributes to early diagnosis, which allows timely treatment and monitoring of patients. Predicting the risks of developing certain diseases based on the identified mutations also helps patients to realize their genetic risks and opportunities for prevention. To solve this problem, the Needleman-Wunsch algorithm is used [2]. However, one of the main problems with this algorithm is its high computational complexity; this algorithm has quadratic complexity. The latter makes it difficult to process large DNA sequences. The development of a parallel algorithm can reduce the execution time by simultaneously processing parts of the data [3], [4], [5]. Ensuring efficient parallelization requires balanced load distribution among threads to prevent idle time, which may involve optimizing data structures and algorithms. Proper synchronization is also essential to avoid conflicts when accessing shared resources, especially in algorithms with interdependent results. Maintaining result accuracy during parallel processing may require extra validation. Lastly, scalability is a key factor. It should be able to scale across different hardware platforms, from personal computers to supercomputer clusters, to achieve optimal results in different environments [6], [7].

Solving all the problems described above is an important step to improve the speed and accuracy of chromosomal abnormalities diagnosis, which, in turn, will increase the efficiency of genetic research and clinical practice.

In the field of genetic research, there are many important aspects that relate to the study of genetic mutations, their diagnosis, and their impact on human health. Various articles offer valuable insights that emphasize the importance of such mutations in medicine, evolution, and biology. For example, paper [8] discusses the work of the Human Gene Mutation Database (HGMD), which collects and analyzes information about human genetic mutations. The authors describe the functions of the HGMD, its use in clinical diagnostics and research, as well as plans to expand the database, which include the integration of GTEx project data and the introduction of automated tools for mutation prediction. The advantages of the article are a detailed overview of the HGMD functions and an emphasis on its role in clinical practice, but the disadvantages are the complexity of automatic identification of new mutations and the lack of examples of real-world use of the HGMD in clinical cases.

In [9], the authors analyze different types of genetic mutations and their impact on human health, including the occurrence of diseases due to mutations in genes or chromosomes. The advantages of this article are a clear description of the causes and consequences of genetic diseases, as well as a detailed overview of the types of mutations. However, there are also disadvantages, such as general statements that are not always supported by specific data, as well as a lack of details about research methods. Nevertheless, the article is useful for familiarizing oneself with genetic mutations and their impact on the human body.

Paper [10] investigates the use of biodosimetry to assess radiation doses in US military personnel who participated in nuclear tests after World War II. The main goal of this study is to assess chromosomal aberrations, such as inversions and translocations, as a method of retrospective biodosimetry. The results show that inversions can be an effective way to establish radiation doses received decades ago and that their combination with translocations improves the accuracy of the estimate. The study also indicates the influence of age and smoking status on the frequency of aberrations, which is higher in older individuals and smokers.

The PETI method is discussed in [11]. It effectively induces precise DNA recombinations in human cells. PETI successfully generates recombination and inversion mutations in endogenous genomes and can correct disease-related inversions and translocations, making it promising for disease modeling and therapeutic approaches. This method is characterized by high accuracy and flexibility compared to other genome editing methods such as Prime-Del and twinPE, but it is still limited in its use for episomal mutations and requires further research to confirm its results.

The authors of [12] investigate the effectiveness of the third generation of sequencing analysis for detecting breakpoints in unbalanced chromosomal translocations. The use of Nanopore long reads allows for the detection of microdeletions, microinsertions, and other structural changes that complement translocations. This approach provides accurate genetic information necessary for diagnosis and treatment. However, the high cost and possible experimental failures point to the need for further research and optimization of methods.

The paper [13] discusses the role of chromosomal rearrangements in the genetic differentiation and evolution of populations, in particular, using the example of the spiny frog with a chromosomal translocation polymorphism. The authors use whole-chromosome staining (WCP) and genetic analysis to confirm the common origin of the translocations. They found that translocated chromosomes have a higher level of genetic differentiation due to recombination suppression, which contributes to genetic diversity and population differentiation. The article also discusses the mechanisms of recombination suppression, such as the accumulation of repetitive sequences and the capture of adapted alleles.

This review is rounded off by article [14], which analyzes the importance of chromosomal inversions in the plant kingdom and their role in plant evolution. The authors note that inversions are common in many groups of plants and are often associated with locally advantageous traits that promote adaptation and speciation. The article also discusses methods for detecting inversions, such as karyotyping, genetic mapping, and high-fidelity sequencing. The authors call for further research to better understand the origin, evolutionary role, and molecular mechanisms of inversions in plants.

Thus, the analysis of scientific studies shows that existing approaches to diagnosing and predicting chromosomal inversions and translocations have their advantages, but also significant disadvantages. For example, the HGMD database, although providing useful information for clinical practice, faces problems with the automatic identification of new mutations. The use of biodosimetry to estimate radiation doses, in particular by analyzing chromosomal aberrations, has proven effective, but is dependent on factors such as age and smoking status. The PETI method demonstrates high accuracy in genetic editing, but requires additional research to confirm its widespread use. Chromosomal rearrangements confirm their role in the genetic differentiation of populations, but require a deeper study of the mechanisms of recombination suppression. The study of inversions in plants also emphasizes the need for further research into the evolutionary mechanisms of these changes. This confirms the importance of continuing research in this area. In particular, the need to develop a parallel algorithm for the diagnosis and prediction of chromosomal inversions and translocations is driven by the need for faster and more accurate detection of genetic abnormalities, which is critical for effective treatment and management of diseases.

The main contribution of this paper:  A new parallel method for detecting chromosomal translocations and inversions using multithreading and parallel computing (OpenMP) is proposed. This method ensures optimal load distribution between threads, reducing processing time and increasing scalability.  The Needleman-Wunsch alignment method has been parallelized to compare sequences, which has increased the accuracy of translocation detection. This approach allows for more accurate identification of chromosomal abnormalities, outperforming traditional sequential alignment methods.  When using eight threads, the proposed method achieves speedups of up to 3.8 for translocations and 3.4 for inversions. This confirms its suitability for processing large amounts of data and the possibility of further optimization on multi-core or GPUs.

Methodic and materials 2.1. General scheme of the method for detecting chromosomal mutations

The task is to develop a method for detecting mutations in DNA sequences. There are two sets of DNA for inversion and four for translocation: half of them are taken as a reference, i.e. without mutations, and the rest with mutations. This method should be able to detect two types of mutations: inversions and translocations.

Let � and � be DNA sequences of length � and �, respectively, �=(� 1 , � 2 , ..., ��) and �=(� 1 , � 2 , ..., ��), where � i and � i take the values {A, C, T, G}. Sequence � is the same sequence �, but at a certain interval from i to i + k the sequence is inverted, i.e. �[i:i+k] ! �[i:i+k] and �[i:i+k] = reverse(�[i:i+k]). To search for inversions, the algorithm comparing two DNA sequences is parallelized. This algorithm detects mismatches in nucleotide sequences and determines the gaps where nucleotides in DNA molecules do not match. After that, the found gaps are checked for inversions. The result of this check is the determination of the gaps where inversions are detected.

To search for translocations, we need to parallelize the Needleman-Wunsch algorithm, which consists in constructing an optimal alignment, using the optimal alignments of the initial fragments of the original sequences obtained in the previous steps. For two sequences � and � with elements � I (0<i<n ) and � j (0<j<m), we construct the matrix F. The element of this matrix contains the weight (score) of the best alignment of elements � 1 , � 2 , ..., � i and � 1 , � 2 , ..., � j of the sequences � and �, respectively. We build the matrix F recursively. We assign the starting point zero weight F(0,0)=0. Then we fill in the matrix in ascending order of both indices, i.e. from the upper left corner to the lower right. If we have already defined F(i-1 ,j-1), F(i-1, j), F(i, j-1), then we can define F(i, j), as

� �, � = 푚� � � − 1, � − 1 + � � , � � � � − 1, � + � � �, � − 1 + �

, where:

 � �, � -the value in the alignment matrix in the position �, � ;

 �( � , � � ) -the value of the penalty (or reward) for matching (match/mismatch) characters � and � � ;

 � -the value of the gap penalty, which can be negative or positive. This formula recursively calculates the values in each cell of the alignment matrix � �, � , considering the three possible ways to reach the current cell: diagonally (matching), vertically (insertion/deletion in the first sequence), and horizontally (insertion/deletion in the second sequence). Figure 1 shows a general flowchart of the chromosomal mutation detection algorithm

Parallelizing the detection of chromosomal inversions and translocations

This paper uses OpenMP technology to detect chromosomal inversions and translocations in the genome. OpenMP allows parallelization of the code, reducing computation time and increasing program efficiency. Testing on a different number of threads showed a significant speedup of the algorithm. By working with shared memory, OpenMP simplifies the exchange of data between threads, which helps to synchronize them.

The main work of the algorithm for finding chromosomal inversions can be divided into two steps:

1. Detection of chromosomal inversion gaps.

Analysis and verification of the results.

The detection of chromosomal inversion gaps is performed by comparing the reference with the target in order to detect mismatches. Accordingly, in a sequential algorithm, the search is performed from the beginning of the array to its end (see Figure 2). This process was parallelized. The array is divided into N intervals of equal length, where N is the number of threads. Accordingly, having a gap length of 2000 characters and N = 4, each thread will search for a gap of 500 characters. Each thread will store the found gaps in its own array and, upon completion of execution, add it to the general array for further processing.

To parallelize the algorithm, we used the schedule(static, chunkSize) directive, which statically distributes tasks between threads. chunkSize -the size of the block that will be processed by a particular thread. The use of the static parameter ensures that the intervals will be consistent. Visualization of the search for inversion gaps in the parallel algorithm is shown in Figure 3. Another resource-intensive process is the analysis and verification of the found inversion gaps. To speed up this process, we perform an initial check to see if the detected nucleotide sequence in the target is an inversion of the corresponding nucleotides in the reference. If the condition is met, we save the gap in the format (start, end, inversion), where the start is the beginning, the end is the end of the gap, and inversion indicates that this nucleotide sequence is an inversion and no further processing is necessary. Otherwise, additional analysis is required.

Additional analysis includes merging gaps and checking the newly formed sequences for inversion. This process cannot be parallelized and is identical to that of the sequential algorithm [15], [16].

The sequential algorithm for finding translocations involves the use of the Needleman-Wunsch method, which consists of sequentially calculating the elements of a matrix based on previously found matrix values. The idea of parallelizing this algorithm is to calculate a specific row or column of the matrix in a separate thread (see Figure 4). With this implementation, the problem of a resource race arises. It is necessary to assume that all three elements that are used to calculate a particular (i; j) element of the matrix are calculated. For this logic, the matrix is used to identify whether the (i; j) element is calculated or not. Waiting for the necessary elements is realized by means of a spin lock, the essence of which is to place the thread in a loop that constantly checks the necessary condition for calculating the element.

To parallelize the algorithm, we used the schedule(static, 1) directive, which statically distributes tasks between threads. Using the static parameter ensures that the work for the threads is distributed evenly, and the second parameter ensures that each subsequent row or column is calculated under a different thread.

Results

The data for testing were taken from the DNA sequence dataset [17]. This dataset is a dataset that contains DNA sequences and contains information about nucleotide sequences consisting of four possible bases: adenine (A), cytosine (C), guanine (G), and thymine (T).

First, we present the results of the parallel algorithm using OpenMP technology to find inversions and translocations (see Table 1 and Table 2, respectively). The program execution time will depend on the number of threads and the number of sequences in the file. 1, it can be concluded that parallelization is not advisable for small values of n, and the calculation speed improves with increasing data volume. Similarly, Table 2 shows that a small matrix dimension is not optimal for a large number of threads. Similarly to the algorithm for detecting inversions for translocations, the parallelization efficiency improves with increasing data size.

Further, based on the results obtained, we calculate the speedup

� � = � � (�) � � (�)

and efficiency

� � = � � (�)

�

of the proposed parallel method, where � � (�) -the execution time of the sequential algorithm, � � (�) -the execution time of the parallel algorithm, and � is the number of threads. The results are shown in Table 3 and Table 4 0.48 From the results, we can see that the proposed parallel method yields good speedup and efficiency with increasing number of threads and input data dimensionality, which indicates that the method is well scalable. It should be noted that all experiments were performed on a computer with eight logical processors. Therefore, they can be significantly improved with a more powerful computing system. The paper also investigates the accuracy achieved by the proposed approach for finding inversions and translocations. To do this, the program was run 1000 times with different lengths of DNA sets with pre-introduced mutations randomly, and the final result was calculated as an average. Table 5 presents the accuracy results of the proposed method on different data sizes, and Table 6 compares the accuracy of the Smith-Waterman algorithm [18] and the Needleman-Wunsch algorithm.

Conclusions and future research

In this paper, we investigated the effectiveness of parallel algorithms for detecting chromosomal mutations, such as inversions and translocations, using OpenMP technology. The algorithms were developed to compare DNA sequences and detect deviations in nucleotide sequences, which allowed for high accuracy in identifying inversions. For translocations, the parallel Needleman-Wunsch algorithm was used to ensure optimal alignment of DNA fragments. Numerical experiments demonstrated a significant performance improvement on different datasets: the best performance was 3.4 for inversions and 3.8 for translocations, achieved using eight threads. The results indicate an improvement in performance with increasing amounts of input data and the possibility of further optimization of the results obtained through the development of multi-core computing systems. To further improve the efficiency of the developed algorithm, we can consider its implementation on a graphics processing unit using CUDA technology, which will potentially provide even higher data processing speed.