# An Improved Strategy for Task Scheduling in the Parallel Computational Alignment of Multiple Sequences

Authors: Muhammad Ishaq; Asfandyar Khan; Mazliham Mohd Su’ud; Muhammad Mansoor Alam; Javed Iqbal Bangash; Abdullah Khan
Journal: Computational and Mathematical Methods in Medicine
 (2022)

---

## Abstract

Task scheduling in parallel multiple sequence alignment (MSA) through improved dynamic programming optimization speeds up alignment processing. The increased importance of multiple matching sequences also needs the utilization of parallel processor systems. This dynamic algorithm proposes improved task scheduling in case of parallel MSA. Specifically, the alignment of several tertiary structured proteins is computationally complex than simple word-based MSA. Parallel task processing is computationally more efficient for protein-structured based superposition. The basic condition for the application of dynamic programming is also fulfilled, because the task scheduling problem has multiple possible solutions or options. Search space reduction for speedy processing of this algorithm is carried out through greedy strategy. Performance in terms of better results is ensured through computationally expensive recursive and iterative greedy approaches. Any optimal scheduling schemes show better performance in heterogeneous resources using CPU or GPU.


---

## Body

## 1. Introduction

This research paper proposes a novel dynamic programming-based task scheduling for parallel multiple sequence alignment (MSA). Further modifications in the proposed algorithms, like iterative, recursive, and greedy strategies, enhance the performance of scheduling in any parallel system. The application of dynamic programming optimization for task scheduling in case of parallelized multiple sequence alignment is preferred over other dynamic task scheduling approaches.The complex issue of task scheduling in any parallel processor system has multiple possible solutions. The structure of a problem like task scheduling can be characterized, then, the application of dynamic programming is the best solution. Multiple alignment operation is divided into pairwise alignments or subparts. Pairwise alignments are interrelated, and the solution of one section can be used in another part of the same problem. The same problems here mean the complete multiple alignment. In this recursion, the intermediate results are stored in a matrix where they can be recalled later in the same program.The storage of profile alignment or intermediate results is different in each individual computational multiple sequence alignment. In dynamic programming, the structure of an optimal solution is characterized, then, the value of an optimal solution is defined recursively, and then an optimal solution is constructed from the computed information. In any array of parallel workers, a master node collects the profile scores. Similarity of sequences is determined from the alignment score or computed information. In dynamic algorithm, the exponential cost is reduced to polynomial type, so more efficient than the ordinary divide and conquer algorithm in terms of time complexity. Dynamic programming application for any stated problem is diagrammatically shown in Figure1.Figure 1
Diagrammatic illustration of the conditions for the application of dynamic programming optimization.Homology modelling or potential orthologues and paralog description is also possible on the basis of protein structure comparison [1].In a given protein structure, if the amino acid shows the interaction or association with other subunits and different atoms, then, it is called as quaternary protein structure.Primary structure of proteins as visible in Jalview with PDB ID 4HHB. This structure is retrieved from Protein Data Bank (PDB). The primary structure is shown in Figure2. The figure shows sample word-based sequences. Three dimensional protein structure matching is more accurate and comprehensive in terms of structure and function prediction but requires a lot of processing time.Figure 2
Primary structure of human deoxyhemoglobin (4HHB, PDB ID).There are many need-based word-based sequence alignment visualization tools. Figure3 is the visualization of sample dataset. In Bioinformatics, the notion of tertiary structure is usually used for proteins rather than nucleic acids.Figure 3
Dataset from GenBank: the linear nucleotide chain constitutes the primary structure of nucleic acid. Here, nucleotides are represented by their respective word-based symbols.Greedy approach improves the efficiency of the dynamic algorithm by reducing the local maxima or the number of possible choices. Computationally complex recursive and iterative greedy techniques further enhance the application of this hybrid methodology.


## 2. Related Research Work in Parallel Processing of MSA

Remote homologue proteins improve sequence alignment by retrieving structural specifications from multiple structure alignment profiles. Sequences that share the same ancestry are called as homologs, and there are two kinds of homologs, orthologs and paralogs. In one approach, the score functions were combined with a systematic search algorithm. The score functions were based upon the sequence and structural information [2]. Sleater et al. proposed the MSA algorithm to be run in a parallelized fashion with the sequencing data distributed over a computer cluster or cloud-based server farm. The cloud computing technology improves the speed, quality, and capability of MSA. They introduce the next generation of cloud-based MSA algorithm [3]. Some researchers utilize BlueGene/Q or JUQUEEN supercomputing capability to evaluate the performance of parallel multiple sequence alignment. A parallel I/O interface for simultaneous and independent access to a single files collectively has been designed and verified [4]. Diaz and his coresearchers developed MC64-ClustalWP2 as a new implementation of ClustalW algorithm. They integrate a novel parallelized strategy that significantly increases the performance of alignment. The proposed method is useful when aligning long global sequences by using multicore architecture or with many processor cores [5]. Their hardware and software feature analysis were carried out for the exploitation and optimization of full potential in case of a parallelized system. To test the performance of their proposed algorithm, they use a hybrid computing system. The researchers counted manifold benefits of MC64-Clustal WP2 [6]. To improve the scalability of global sequence alignment, an MPI-based parallelization technique is proposed. In this method, a parallel waveform algorithm based on a chunk size transformation to handle large datasets with message passing model exposes high speed up and scales linearly with the increasing number of processes [7]. Some researchers examine different multicore machines by running a variety of MSA software [8]. In recent years, we observe various kinds of novel techniques for parallel MSA like artificial bee colony optimization [9]. R is extensively used for computational sequence alignment [10].


## 3. Problem Statement regarding Multiprocessor Task Scheduling through Dynamic Programming

In parallel MSA, we deal with the multiprocessor scheduling system. Assume that a set of tasks is to be executed by a parallel system with identical processors. For example, taskXi requires time Ti for execution.Task here means a single pairwise word-based or structure-based alignment. In this case, the precedence of task execution is achieved by a tree or forest of tree data structure. Dynamic programming like genetic algorithm takes in to account all possible candidate solutions, which is not an efficient approach. Figure4 shows the parallel processing of MSA, and each worker is responsible for one PWA at a time.Figure 4
Parallel processing of multiple sequence alignment.


## 4. Application of Dynamic Programming for Task Scheduling Problem in MSA

In case of sequential or parallel processing of each pairwise alignment in MSA, a single task (pairwise alignment) is selected by each processor. Thus, an algorithm based upon dynamic programming can solve the task selection problem. If we have a setS=x1,x2,x3⋯.xn of n tasks. Each pairwise alignment xi has a starting time Si and a finishing time Fi where 0≤Si<Fi<∝. The tasks are sorted with respect to increasing finish time F1<F2<Fn. For scheduling tasks during MSA, the profile makes require the maximum size subset of closely related sequences. The aligned sequences make a profile. Pairwise alignments (tasks) cannot use a given processor at a time. Each task has a corresponding time interval Tj=Sj,Fj during which the processor is busy in executing the task. For a given two tasks xi and xj, the interval Ti and Tj do not overlap, i.e., Si≥FjorSj<Fi. So all tasks for a given processor must be compatible in terms of their ordered time interval.IfXij is the set of all tasks ak in X which is started when ai finishes and finish before task aj starts. Xij=ak∀X:Fi≤Sk<Fk≤Sj here FiandFk denote finish time of ai and ak.SkandSj represent start time of tasks ak and aj. If i=1andj=n then Xij exclude task a1andan.For this purpose, we can define fictitious tasksa0andan+1 such that the finish time of a0isf0=0 and the start time of an+1isSn+1=∝. So 0≤i,j≤n+1 and X0n+1 include all tasks including a1andan.Based uponak task Xij can be divided into XikandXkj. All Xik tasks start after ai finishes and finish execution before ak starts execution. Similarly, all Xkj tasks start execution after ak finishes and finish before aj starts. XikandXkj are subsets of Xij, but Xij≠Xik∪Xkj or Xij=Xik∪Xkj∪ak because ak does not exist in both subsets.A sample parallel web-based reference tree generation of 38 RefSeq Proteins is shown in Figure5.Figure 5
Sample parallel tree generation using estimated Gamma parameters for local aligned site rates.Also, the solution ofXij can also be demonstrated as
(1)SolXij=SolXik∪SolXkj∪ak.IfSolXij is an optimal multiple sequence alignment, then, SolXik and SolXkj are also optimal. If we have another solution SolXik′ for Xik, and we replace SolXik in SolXij with SolXik′ then SolXij′ has more tasks than SolXij.So SolXij is not optimal, and we encounter a contradiction so it is proved that SolXik and SolXkj are also optimal set of tasks.


## 5. Recursive Solution of the above Strategy

Recursion is computationally expensive. Assume thatLi,j is the number of tasks in a maximum size subset of mutually compatible tasks in Xij. If Xij=∅; then, Li,j=0. We know that SolXij=SolXik∪SolXkj∪ak so the recurrence relation for the problem is Li,j=Li,k+Lk,j+1. The recursive definition of Li,j becomes
(2)Li,j=0,ifXij=∅,maxofLi,k+Lk,j+1,ifXij≠∅,i<k<j.There is no restriction of using sequence data sets. Sequences of any specific organism are not mandatory. Figure6 shows the chloroplast protein sequences, and chloroplast is a green pigment in many plants, responsible for photosynthesis.Figure 6
Chloroplast protein sequences of the given plant species.


## 6. Greedy Approach and Its Implications for the Abovementioned Problem

Greedy approach increases the efficiency of the algorithm by reducing the search space and reduces the computational complexity. If we have nonempty subproblemYij and cm is any task in Yij with earliest finishing time. The optimal task or the task with the earliest finishing time (quick execution) is called cm.The following steps should be proved for the application of greedy solution in the abovementioned task scheduling algorithm. Greedy strategy takes into account the most optimal sequences to be aligned with a given MSA profile.In the first step, the determination of the suboptimal structure of the problem is carried out. We have to prove that the taskcm can be used in some maximum size subset of mutually compatible tasks of Yij. And the subproblem Yim is empty, so that choosing cm leaves the subproblem Ymj as the only one that may be nonempty.First of all, we have to prove the second simple problem thatYim is empty. Lets Yim is nonempty, it means that there is some task ak such that fi≤Sk<fk≤sm<fm⟹fk<fm. So ak is also in Yij but its finishing time is less than cm which contradicts with our assumption that cm has the earliest finishing time. We show that there is another task in Yij that has less finishing time than cm, and it proves that Yim is empty.In any approach, the power of computational techniques in case of translation as shown in Figure7 cannot be ignored.Figure 7
Other sequence data export formats available in the majority of web-based implementation tools.For a greedy approach to be applied in this case, we have also to prove thatcm can be used in some maximum size subset of mutually compatible tasks of Yij or cm is a member of one of the optimal solutions. Suppose that Aij is a maximum size subset of mutually compatible tasks of Yij. Order Aij is the monotonic increasing order of finishing time. Let ak be the first activity in Aij with respect to the finishing time. If ak=cm then we already know that and prove it before that cm is used in some maximal subset of mutually compatible tasks of Yij. Therefore, there is nothing to prove, and we show it that there must exist at least one of the optimal solutions which contain the task cm. So cm belongs to Aij optimal solution.Ifak≠cm; then, there must be some other optimal solution where task cm exists. Lets suppose Aij′ is another optimal solution and Aij′=Aij\ak∪cm. Aij tasks are disjoint, and it is true for Aij′. This statement means that cm belongs to Aij′ because we negate cm from Aij′. As ak is the first task in Aij to finish and the finishing time of ak is greater than the finishing time of cmfm≤fk. Here, fmorfk denotes finishing time of ak or cm. So it means that task cm is included in optimal solution set Aij′ and Aij′ is the maximal subset of mutually compatible tasks of Yij. The number of tasks in Aij and Aij′ is the same, and both have the same cardinality. We have proved that Aij′ is a maximal set of mutually compatible tasks. All tasks in Aij′ must be mutually compatible.The conclusion of the above greedy approach is that taskcm belongs to Ymj and Yim=∅. Therefore, it improves the efficiency of greedy approach in case of multitask scheduling algorithm compared to dynamic programming. In dynamic programming, there were two subproblems which were reduced to one by the greedy approach. The number of choices is j−i−1 in dynamic programming, and there is only one choice in the greedy theorem.Greedy algorithms do not work in some cases, i.e., in the cases of longest monotonically increasing subsequences. Suppose that we have a given sequence of <2, 3, 4, 13, 5, 6, 7>, and its longest common subsequence (LCS) is <2, 3, 4, 5, 6, 7>. If we solve this problem with greedy approach then its LCS is <2, 3, 4, 13> which is suboptimal. In greedy approach, the rest of three elements 13 cannot be chosen. Therefore <2, 3, 4, 13> is a monotonically increasing sequence, but it is not the longest monotonically increasing sequence. Figure5 shows the export ability of candidate local optimal (sequences).


## 7. Structure of Recursive Greedy Algorithm for Task Scheduling

At each processor, the algorithm for task scheduling can be defined recursively. Recursive task selectors,f,i.j where s is the set of tasks and f is the finishing time. The initial value of i=0 and j=n+1. We want to determine a task that belongs to the optimal solution. In the process of recursion, there will always be an optimal or greedy choice.Recursive task selectors,f,i.j..Code 1
1.m⟵i+1//m to be the first task in Xij2.whilem<jandsm<fi //find the first task (m) in Xij. Here, sm is the starting time of m.3.dom⟵m+1 And fi is the finishing time of i4.ifm<j5.then6.returnam7.Urecursivetaskselectors,f,m.j //repeat the same process from step 1 to8.elseretun∅Some computational alignment tools have unique ability to show translated proteins of given set of nucleic acid sequences as shown in Figure8. Correct similarity index calculation of a given pairwise or multiple sequence alignment is principally related with gap and gap extension penalty as shown in Figure 9.Figure 8
MSA of DNA sequences and the relevant translated proteins.Figure 9
Pairwise and multiple alignment gap and gap extension penalty features.


## 8. Structure of Iterative Greedy Algorithms for Task Scheduling in Parallel MSA

Iterative algorithms are more efficient than recursive algorithms. Recursive algorithms are computationally more expensive. The above recursive greedy algorithm can be expressed in an iterative manner. In task scheduling, we repeat the same process again and again, so iteration of the same process is computationally efficient. In this case, we have two tasks,s is set of all the tasks, and f is the set of the finishing time of all tasks.Iterative task selectors,f.Code 2
n⟵lengths//compute the total number of tasksSols⟵a1 //sorting of all tasks according to their finishing time. The first task must be a i⟵1 //initialize a variable i (ai is the part of solution) //part of our optimal solution.form⟵2tondoifsm≥fi //here sm is the starting time of m and fi is the finishing time of ithenSols⟵Sols∪ami⟵m //we again select activity amreturnSols //The set of all tasks that are mutually compatible is retrieved. Irrespective of whether recursive, iterative or any other hybrid modification to this approach, gap penalties of PWA or MSA are also essential as shown in Figure 7.


## 9. Implementation Details and Results

Multiple sequence alignment is a tightly coupled processing task, so the application of map-reduce model is not valid in the parallelization of MSA. The task scheduling during parallelization of MSA is based upon a single program and multiple data (SPMD) style. Imagine that the mesh cluster as discussed above is a global matrix ofm∗n dimensions, and individual processors own a different collection of rows in the matrix. In this case, all processors are local, so each dimension receives a general block distribution object. Figures 8 and 9 can explain the strategy.MPI I/O over a subset of MPI cores can also be used to foster file reading in any parallel MSA data set [11].Figure10 shows the famous machine learning approach for estimated diversion time calculation. The proposed scheduling algorithm using dynamic programming has O (nlogn) complexity. Each task or pairwise alignment (PWA) in the profile formation has a start and finish time. During the scheduling of MSA with multiple workers (processors), the goal is to overcome the overlap of any task (PWA) in any subset of the cluster mesh. The algorithm will also calculate the overall multiple alignment score.Figure 10
Estimated diversion time calculation for parallel nucleic acid and protein computational sequence alignment.In Python as a first step, a class task defines the start finish time with the calculated alignment score of each PWA. An iterative binary search is carried out to find the midpoint of any defined task with low and high indexes.Substitution matrices are available in many libraries.Code 3
from pymsa.core.substitution_matrix import SubstitutionMatrix, FileMatrix, PAM250, Blosum62. Specific PAM and BLOSUM are also available for import from pyMSA.A variety of gap penalties can be opted. Some of the gap penalty functions available in Pymsa and other prominent matching libraries are as under.Code 4
gap_penalty_be_minus(),modify_the_gap_penalty(),gap_penalty_if_a_char_is_a_gap(),if_the_two_chars_are_gaps(),if_there_are_no_gaps()Figure11 is the conceptual design of mesh topology for parallel processing system. Some schedulers like the in-process use periodic jobs that use the builder pattern for configuration. These schedulers let you run the respective Python library functions periodically. The periodic time intervals are predetermined using a simple, human-friendly syntax.Figure 11
Mesh type topology in case of cluster for protein structure MSA. One node in each row is a master node [12].In any parallel processing system, the following libraries need to be imported for task scheduling in your work space. These libraries include collections, datetime, functions, logging, random, re, and time.Using Python object-oriented paradigm capability, the ScheduledTask in this case has eight user-defined functions for different operations. The job class has the default scheduler. Typical operations in process scheduling are time interval definition, excuse or run operation, clear cancel job, and the definition of next run. The scheduler also manages free time.The main features of any scheduler should be (but not limited to) an efficient and effective execution of operations. It means fail load distribution and reduction in time complexity. There are simple to use API for scheduling jobs for simulated and real test bids. These API are very lightweight having no external dependencies, excellent test coverage, and tested on all latest Python 3 versions.Tasks are scheduled based upon their finish time. As a convention of dynamic programming, the solutions of subproblems are stored in a matrix. The matrix stores the score of PWA or task till all elements in the array. The store results are used again and again in the profile building process of MSA. The entries in the matrix are filled recursively. At each step of parallel MSA, the alignment score is stored in a matrix. Large alignment scores replace the previous low scoring matrix. Table1 is only for three chloroplast protein sequences that can be extended to other species. Beside unique differences, the table shows identical and divergent sites.Table 1
Similarity parameters in the computational alignment of three chloroplast protein sequences.
Results from the Tajima’s test for 3 sequencesConfigurationCountIdentical sites in all three sequences6261Divergent sites in all three sequences1284Unique differences in sequence A1043Unique differences in sequence B1282Unique differences in sequence C603In the first experiment, four tasks or workers get values. The time complexities remain less than many available optimal dynamic methods for this purpose.Maximum likelihood estimate of Gamma parameter for site rates in case of protein sequences. The estimated value of the shape parameter for the discrete Gamma distribution is 0.5435.Substitution pattern and rates were estimated under the Jones-Taylor-Thornton (1992) model (+G) [2]. A discrete Gamma distribution was used to model evolutionary differences among sites (5 categories, +G). Mean evolutionary rates in these categories were 0.03, 0.18, 0.50, 1.13, and 3.16 substitutions per site.The amino acid frequencies are 7.69% (A), 5.11% (R), 4.25% (N), 5.13% (D), 2.03% (C), 4.11% (Q), 6.18% (E), 7.47% (G), 2.30% (H), 5.26% (I), 9.11% (L), 5.95% (K), 2.34% (M), 4.05% (F), 5.05% (P), 6.82% (S), 5.85% (T), 1.43% (W), 3.23% (Y), and 6.64% (V). For estimating ML values, a tree topology was automatically computed. The maximum Log likelihood for this computation was -119906.071. This analysis involved 10 amino acid sequences.The number of amino acid substitutions per site from mean diversity calculations for the entire population is shown below. Analyses were conducted using the Poisson correction model. This analysis involved 2 amino acid sequences of the original chloroplast proteins. All ambiguous positions were removed for each sequence pair (pairwise deletion option). There were a total of 11039 positions in the final dataset.Code 5
Analysis ====================Analysis= ====================Scope = Average of the overall population of sequencesEstimate Variance = ====================Variance Estimation Method = None(Can be customized)Substitution Model= ====================Substitution Type = Amino acidModel/Method = Poisson modelRates and Patterns = ====================Rates among Sites = Uniform RatesPattern among Lineages = Same (Homogeneous)Data Subset to Use= ====================Gaps/Missing Data Treatment = Pairwise deletionNo. of Sites:11039 d:EstimatePseudomonas keratins multiple sequence alignment is shown in Figure12. Optimal regions matching in any MSA depict the quality of algorithm.Figure 12
Graph showing results of six selected (NCBI GenBank) keratins (proteins) for MSA (word based).Disorder comparison at each node of individual pairwise alignment is shown in Figure13.Figure 13
Graphs show pairwise aligned protein sequences from each node in parallel system with disorder comparison at the middle of image.


## 10. Discussion

Three dimensional comparisons of biological sequences involve the calculation of root mean square deviation, and parallelization of multiple protein 3D structure alignment reduces computational. This paper concludes a new technique for parallel MSA task scheduling using dynamic programming optimization in heterogeneous environments.There are multiple choices during the scheduling of sequence matching tasks, so the application of dynamic programming (DP) is justified. DP is also used as a base method for computational sequence alignment. To further reduce the computational cost and to limit the number of candidate solutions, a greedy strategy is applied. Greedy approach does not take into account all candidate solutions in a single run.Recursion and iteration solve the issue of optimal alignment score, but computationally expensive. In the era of fast processing machines, the greedy technique is not an efficient selection. Iteration is an efficient approach for optimal alignment and fair load distribution during parallel MSA task scheduling.



---

*Source: 8691646-2022-01-28.xml*