BACKGROUND
genetic and protein sequences are being discovered rapidly, and as a result, the number of sequences entered into biological databases is growing exponentially over time.
most of the work currently being done in computational biology involves searching for inter- and intra-sequence homology in massive volumes of genetic and protein sequence data, which are commonly based on a multiple sequence alignments   <cit> .
however, increasing the computational efficiency to solve a variety of real msa problems is still a challenging task because of the high demand for greater capacity and speed  <cit> .
the oldest and most widely used msa program that estimates trees as it aligns multiple sequences is clustalw  <cit> .
clustalx is an integrated graphical-user-interface  version of the clustalw multiple sequence alignment program  <cit> .
it provides an easy-to-use work environment for performing msa and pattern analyses.
the latest version of clustalx  added two new features  <cit> .
the main advantage of clustalx  <dig>  is that it provides an easier way to maintain code for other applications.
the new guided-tree implementation, compared with the older version, enables larger, faster computations.
clustalx  <dig>  is now available for a number of platforms, including sun solaris, irix <dig>  on silicon graphics, digital unix on decstations, microsoft windows for pcs, linux elf for x <dig> pcs, and macintosh powermac.
unfortunately, most of the currently available msa programs are not suitable for large-capacity data storage and massive computation.
these programs, including clustalx , are still single-pc based, and the storage and computation is entirely dependent on physical random-access memory .
past msa performance evaluations focused simply on how compute-intense and sensitive the program was with respect to the longest-common-sequence -based exact-string matching algorithm   <cit> .
depending on both the volume of data to be aligned and the accuracy of the comparisons, computation using dynamic programming is extremely time-consuming when large sequence volumes and high accuracy are required simultaneously.
numerous parallel-computation programs, such as parallelized praline  <cit> , dialign p  <cit> , clustalw-mpi  <cit> , and a commercial sgi parallel clustal on a shared memory sgi multiprocessor  <cit> , have been developed, primarily to increase computational speed, rather than for larger capacity data handling.
multiple sequence alignments with the clustal series programs and the required features have been reviewed  <cit> .
in this study, we report clustalxeed, which was designed for a wide range of msa purposes .
this is a new ultra-high grid version of clustalx supports both a large-scale msa and efficient load-balancing.
we also evaluated its overall performance using a typical grid-computation system.
clustalxeed is currently available for linux 64-bit/32-bit platforms.
a major point we emphasize is that clustalxeed provides dual-mode sequence loading and computation platforms, where if the size of the biological sequence exceeds the available ram, the user can readily shift to a distributed file-allocation  mode.
the disk-storage system uses an idle node-seeking task algorithm , which forces sleeping nodes into active modes during the massive file-swapping and pair-align computation to overcome slow computation speed.
the gui-based parallel-computation system is implemented with linux and can be classified into two subsystems: the gui engine  for interactions between users and the parallel-computation system, and the pair-alignment engine for the calculation of pair-align matrices.
implementation
dual computation mode: single or parallel central processing units
clustalxeed assigns two computation platforms incorporating physical ram addressing, using a modified version of the clustalw-xeed_mem file, which is similar to the original clustalw or clustalw-mpi tools  <cit>  and distributed file allocation, using the clustalw-xeed file.
the new clustalw-xeed file enables large-scale disk memory storage and smart allocation of vast sequence data sets to a disk swap space for construction of temporary pair-align matrices and for accelerated computation.
clustalxeed uses a sequential file writing method that provides a straightforward and efficient way to read and write files.
for a large number of sequences, clustalxeed converts input sequences into individual sequence pairs and stores the pairs using the naming rule/tmp/xxxxx000p, where p = the pair sequence number and the generation number of the file name is always + <dig>
a distance matrix file, which is a single file with a file name of matrix-file <dig> tmp, is also generated in a disk storage unit and is based on all-to-all pair sets from the input sequence query.
the calculated pair scores generated from each computation node are stored in the master node/tmp directory.
creation of this process involved modification of the three main programming functions in the original clustalw , as well as the pairalign message-passing-interface  algorithm in clustalw-mpi  <cit> .
for cluster analysis, clustalxeed uses the distance matrix and the neighbor-joining clustering method to construct a similarity or guided tree.
during this step, temporary changes in tree values are recorded sequentially by creating a new similarity tree file that contains the updated records at each computation stage.
this technique provides an efficient file handling methodology for analyses involving frequent writing/reading of large data sets, as is required for dynamic programming using the sum of pairs  scoring method.
the similarity matrix files generated at each stage are named using the same naming rule as was described for the input file storage system.
the final multiple sequence alignment  results are stored in a {*.aln} file for easy data retrieval.
dynamic scan load balancing
both clustalw and clustalx calculate pair-align scores to generate a guided tree for multiple sequence alignment.
during this step, a distributed computation strategy may accelerate the computation.
this means that the performance of any distributed parallel-computation approach depends on the balance of the workloads among the distributed nodes .
in an ideal case, the sequence of the elements to insert is uniformly divided between the work-node threads.
depending both on the volume of the data to be aligned and the accuracy of the comparisons, computation by dynamic programming requires time-consuming iterations to achieve high accuracy.
as an example, clustalx has a parallelized version of clustalx irix that is optimized to run on sgi origin parallel computers running irix  <dig> .
the main problem of this parallelized version, however, is that the user has to spend extra time pre-sorting the input data to reduce load imbalances.
if the overall pair-align computation nodes are well balanced, performance will be greatly improved .
the effect becomes dramatic when input sequences dominate the computation time, due to excessively long or short strings.
this is necessary in the case of highly parallel file-swap systems where load balancing is a key speed-up feature for performance enhancement.
physical ram addressing is preferred for small-to-medium-sized sequences, whereas the file-swap  system is used for very large volume computations.
to overcome the slow speed of the file  memory computation, we designed an efficient load balancer, which uses a fast, intelligent scanning strategy to find sleeping computation nodes.
based on the previous distribution characteristics of clustalw-mpi, we propose a dynamic scan-load balancing algorithm for efficient job-assignment of non-uniformly  distributed pair-align computation nodes, which is specified to increase the speed of interprocessor  communications .
the original parallel version of clustalw-mpi uses a fixed-size chunk scheduler algorithm to distribute sequence pairs to each node  <cit> .
the main job of the master node in our system is to keep the slave nodes busy, as long as there is work to be done.
that is, when a computation node completes its processing, it requests additional cue-sequence pairs from the master.
this form of dynamic load-balancing continues until all of the sequences have been aligned.
once the job is submitted, it can be monitored and controlled via clustalxeed main.
new features in clustalxeed core
new sequence editing options
clustalxeed allows the user to change the order of sequences by simply cutting and pasting the sequence names.
the sequence block grabber also provides a box-shaded area that enables the user to realign badly aligned sequences in a new window format, and to realign a small box region again.
this option provides an independent task for the refinement of aligned sequences.
the realignment range can be selected by simply clicking the mouse and dragging on the new sequence area .
easy sequence finder enables a search for nucleic acids or proteins based on a partial sequence input.
phylogenetic tree view option enhanced
for the convenience of direct tree-drawing, treeview  <cit>  open source was embedded because some environments cannot read "unweighted pair group method with arithmetic mean"  trees.
this was a known problem in the previous versions of clustalx and clustalx  <dig> .
users can save the resulting tree image as a postscript {*.ps} file.
clustalxeed supports standard truetype and postscript fonts, which may increase the resulting tree resolution when enlarged, especially in the case of a huge sequence data set.
real-time in-process dialogue box
a real-time in-process dialogue box was built to enable the user to quickly monitor the current status of the computation, the progression of the job, and information on the number of nodes involved in the calculation.
neither clustalx nor x <dig>  gives feedback on the computation status.
when the msa is finished, the user can save all of the computation history to a {result.log} file.
the used parameters are also saved in the working directory as a {result.par} file.
this allows a user to view and edit tag information about all the individual batch sequence-alignment jobs.
secondary structure prediction
the gor iv  <cit>  and phd  <cit>  options were added, although their installation requires permission from the original developer.
we do not provide this permission in clustalxeed.
protein weight matrices
clustalxeed provides more options for selecting protein-weight matrices.
the former version of clustalx  provides only three different protein-weight matrices: blosum  <dig>  pam  <dig>  and gonnet  <dig>  we added more than  <dig> different types of protein-weight matrices for specifying scoring tables for the easy and accurate adjustment of sp score improvement.
this allows the user to reduce or increase the multiple sequence alignment sensitivity.
RESULTS
clustalxeed allows the alignment of large numbers of nucleic acid or protein sequences.
generally, the memory space requirement for the dynamic programming algorithm follows o .
based on this, for over  <dig> sequences, msa requires at least  <dig>  terabytes of memory  just to construct a distance-tree matrix, regardless of sequence length.
we evaluated our software using large volumes of real nucleic acid and protein data sets to assess its overall and detailed performance.
we set up a typical  <dig> × cpu amd opteron  <dig>  64-bit cluster system with linux .
the master node consists of a 10-terabyte hdd : 3ware raid adapter  and  <dig> gb dram, for a huge-tree matrix construction.
each node is a dual-core opteron system with  <dig> gb dram and a 1-terabyte hdd.
to confirm the full sequence-loading and speed-up computation, almost six million sequences  in an nt.gz file were first downloaded from ftp://ftp.ncbi.nih.gov/ blast/fasta.
these dna sequences were divided into smaller data sets containing  <dig> to  <dig> sequences.
with  <dig> sequences as the first test set, which requires a nearly 8-terabyte file-managing environment for the msa job, the elapsed computation time was  <dig> - to 6-times shorter than that without insta.
the total execution time for the complete alignment of  <dig>  nucleic acid sequences by the disk-storage system was about 4700- <dig> s with insta, and 7500- <dig> s without insta.
once the insta was built, the overall speed-up rate was directly increased with the added computation nodes.
the total computation efficiency depends on the pair-align scoring stage .
for a given number of sequences, the average speed of clustalxeed performance increased with the number of computation nodes .
as a second performance test, we extracted from ncbi a data set comprised of  <dig>  protein sequences from the cytochrome p <dig> superfamily.
the average length of the protein sequences was  <dig> amino acids , with minimal length around  <dig> aa and maximal length of  <dig> aa.
in total,  <dig> × <dig>  pair-wise sequence alignments are required to complete each sp score calculation.
we randomly mixed all of these sequences and aligned them using the disk-storage system.
figure  <dig> summarizes the obtained execution times of different job-balancing conditions as a function of node numbers.
when the load-balancing algorithm was applied, the execution time of clustalxeed was more than four times faster than the usual file-swap mode.
the average speed-up for  <dig> nodes was  <dig>  with insta and  <dig>  without insta.
the observed speed-up difference was due to the efficient load-balancing of sparsely distributed sequence pairs, and it clearly demonstrated the success of the implemented load-balancing algorithm.
we showed that there exists an optimal node number to be assigned to jobs for the effective usage of computation resources.
it is important to determine what system size will result in the maximum speed-up.
the speed-up rate, as a function of participating node numbers, was not linear, because there was implicit waiting time due to communication latency .
all pairs of sequences in the clustalxeed main disk-storage are transferred to compute nodes, and the calculated pair scores are then returned to the master and are saved in the disk-storage distance matrix .
CONCLUSIONS
clustalw is the most widely used multiple sequence alignment program.
the program uses a profile-based progressive alignment, with the alignment process divided into three steps:  distance matrix/pair-wise alignment,  guided tree generation, and  progressive alignment.
however, clustalw is not capable of estimating phylogenies and alignments for large data sets, because of slow computation times and limited memory usage.
alternatives to clustalw include clustalx , a graphical user interface -based version of clustalw, and clustalw-mpi, a recently developed, parallel implementation version of clustalw.
in the latter tool, all three required computation steps are performed in parallel to reduce the total computation time.
for parallel job scheduling, clustalw-mpi uses a fixed-size chunk scheduler, which divides each job into uniform, fixed sizes.
this method of batch job scheduling sometimes reduces the communication overhead required for a small and moderate number of sequences having very short lengths, such as ests .
however, it is not always effective at balancing the workload required for a large number of sequences having unequal lengths.
under these circumstances, the iteration for the next job scheduling is often delayed, which may result in high processor idle time  <cit> .
moreover, because clustalw-mpi uses a ram memory-storage mode, it has the inherent problem of a shortage of memory available for large-scale data sets.
clustalxeed was designed to simultaneously address the dual needs of fast computation and large sequence data handling.
core changes with significant strides in supporting disk-memory access capabilities and enhanced job scheduling can tackle this bottleneck by enhancing both storage capacity and speed.
as mentioned previously, clustalw-mpi delivers fixed-size chunks to every compute node before the calculation.
the batch scheduling mode needs high memory on each node, which may result in processor idling when the sequence lengths are not uniform.
in contrast, the clustalxeed disk storage algorithm does not send all pair sequences to the computation nodes and instead master allocates  the pair sequences individually to an appropriate node using a load-balancing idle node-seeking task algorithm  to reduce the initial file transfer cost and slave node memory requirements.
clustalxeed also provides a fixed size chunk algorithm in the memory-storage mode for alignment of small-to-medium-sized sequences.
because clustalxeed was designed to work at the capacity of disk memory space, it has no inherent limitation on input sequence amounts.
with a 64-bit compiler version, clustalxeed works with sequence arrays containing up to  <dig> terabytes in disk-storage mode.
in the disk memory operation, alignment speed was also improved by incorporating insta, which allocates or re-allocates tasks to idle nodes during pair alignment without the requirement for prior task information.
in this way, insta determines from moment to moment which imbalanced nodes can be resolved immediately by allocating a new job.
the main advantage of insta is its prompt scanning and decision-making without requiring decision complexity of rescheduling or reallocating tasks to resources at runtime, as occurs with static or other general dynamic load-balancing algorithms.
while setting up a new sequence batch job, the user has the option to choose an appropriate alternate computing environment using the graphical menu option.
other precise values of multiple sequence alignment tuning parameters can be set for each clustalxeed menu link individually .
users can follow the progress of their alignment execution from the real-time in-process dialogue box.
as indicated previously, the new parameter inputs, the easy-to-use realign option, the fully integrated graphical user interface, and the improved speed-up performance for very large volumes of sequence data may provide optimized computation of biological sequence alignments.
clustalxeed demonstrates that the embedded insta is a simple and effective means to meet the high computational demands  for massive biological-sequence alignments.
moreover, large phylogenetic tree construction is becoming increasingly important, as vast amounts of biological sequences are used in the evolutionary and functional analysis of grouping organisms.
clustalxeed provides a great opportunity for the discovery of large and reliable phylogenetic trees between interesting biological sequence data sets.
based on the combination of  <dig> new protein-weight matrices, encouraging results show that clustalxeed is one of most powerful msa tools available for the rapid construction of huge phylogenies.
availability and requirements
project name: clustalxeed.
project home page: http://pchm.inje.ac.kr/clustalxeed.
operating system: runs both on single and parallel linux-based clustal systems.
programming language: c-language, message passing interface .
other requirements: described in the project home page.
more detailed installation instructions and a tutorial manual will also be available for download.
license: clustalxeed is available in source code, without fee, for academic, non-profit uses.
the program is distributed in the hope that it will become further improved and put to practical use.
abbreviations
hpc: high performance computing; gui: graphical user interface; msa: multiple sequence alignment; mpi: message passing interface; ram: random access memory; insta: idle node-seeking task algorithm; cpu: central processing unit; hdd: hard disk drive; i/o: input/output; malign: multiple alignment; sp: sum of pairs
authors' contributions
hj designed and wrote the software, with support from tk.
both authors contributed to the writing of the manuscript.
all authors read and approved the final manuscript.

 genetic and protein sequences are being discovered rapidly, and as a result, the number of sequences entered into biological databases is growing exponentially over time. most of the work currently being done in computational biology involves searching for inter- and intra-sequence homology in massive volumes of genetic and protein sequence data, which are commonly based on a multiple sequence alignments. however, increasing the computational efficiency to solve a variety of real msa problems is still a challenging task because of the high demand for greater capacity and speed. the oldest and most widely used msa program that estimates trees as it aligns multiple sequences is clustalw. clustalx is an integrated graphical-user-interface version of the clustalw multiple sequence alignment program. it provides an easy-to-use work environment for performing msa and pattern analyses. the latest version of clustalx added two new features. the main advantage of clustalx is that it provides an easier way to maintain code for other applications. the new guided-tree implementation, compared with the older version, enables larger, faster computations. clustalx is now available for a number of platforms, including sun solaris, irix on silicon graphics, digital unix on decstations, microsoft windows for pcs, linux elf for x pcs, and macintosh powermac. unfortunately, most of the currently available msa programs are not suitable for large-capacity data storage and massive computation. these programs, including clustalx, are still single-pc based, and the storage and computation is entirely dependent on physical random-access memory. past msa performance evaluations focused simply on how compute-intense and sensitive the program was with respect to the longest-common-sequence -based exact-string matching algorithm. depending on both the volume of data to be aligned and the accuracy of the comparisons, computation using dynamic programming is extremely time-consuming when large sequence volumes and high accuracy are required simultaneously. numerous parallel-computation programs, such as parallelized praline, dialign p, clustalw-mpi, and a commercial sgi parallel clustal on a shared memory sgi multiprocessor, have been developed, primarily to increase computational speed, rather than for larger capacity data handling. multiple sequence alignments with the clustal series programs and the required features have been reviewed. in this study, we report clustalxeed, which was designed for a wide range of msa purposes. this is a new ultra-high grid version of clustalx supports both a large-scale msa and efficient load-balancing. we also evaluated its overall performance using a typical grid-computation system. clustalxeed is currently available for linux 64-bit/32-bit platforms. a major point we emphasize is that clustalxeed provides dual-mode sequence loading and computation platforms, where if the size of the biological sequence exceeds the available ram, the user can readily shift to a distributed file-allocation mode. the disk-storage system uses an idle node-seeking task algorithm, which forces sleeping nodes into active modes during the massive file-swapping and pair-align computation to overcome slow computation speed. the gui-based parallel-computation system is implemented with linux and can be classified into two subsystems: the gui engine for interactions between users and the parallel-computation system, and the pair-alignment engine for the calculation of pair-align matrices. implementation dual computation mode: single or parallel central processing units clustalxeed assigns two computation platforms incorporating physical ram addressing, using a modified version of the clustalw-xeed_mem file, which is similar to the original clustalw or clustalw-mpi tools and distributed file allocation, using the clustalw-xeed file. the new clustalw-xeed file enables large-scale disk memory storage and smart allocation of vast sequence data sets to a disk swap space for construction of temporary pair-align matrices and for accelerated computation. clustalxeed uses a sequential file writing method that provides a straightforward and efficient way to read and write files. for a large number of sequences, clustalxeed converts input sequences into individual sequence pairs and stores the pairs using the naming rule/tmp/xxxxx000p, where p = the pair sequence number and the generation number of the file name is always + a distance matrix file, which is a single file with a file name of matrix-file tmp, is also generated in a disk storage unit and is based on all-to-all pair sets from the input sequence query. the calculated pair scores generated from each computation node are stored in the master node/tmp directory. creation of this process involved modification of the three main programming functions in the original clustalw, as well as the pairalign message-passing-interface algorithm in clustalw-mpi. for cluster analysis, clustalxeed uses the distance matrix and the neighbor-joining clustering method to construct a similarity or guided tree. during this step, temporary changes in tree values are recorded sequentially by creating a new similarity tree file that contains the updated records at each computation stage. this technique provides an efficient file handling methodology for analyses involving frequent writing/reading of large data sets, as is required for dynamic programming using the sum of pairs scoring method. the similarity matrix files generated at each stage are named using the same naming rule as was described for the input file storage system. the final multiple sequence alignment results are stored in a {*.aln} file for easy data retrieval. dynamic scan load balancing both clustalw and clustalx calculate pair-align scores to generate a guided tree for multiple sequence alignment. during this step, a distributed computation strategy may accelerate the computation. this means that the performance of any distributed parallel-computation approach depends on the balance of the workloads among the distributed nodes. in an ideal case, the sequence of the elements to insert is uniformly divided between the work-node threads. depending both on the volume of the data to be aligned and the accuracy of the comparisons, computation by dynamic programming requires time-consuming iterations to achieve high accuracy. as an example, clustalx has a parallelized version of clustalx irix that is optimized to run on sgi origin parallel computers running irix. the main problem of this parallelized version, however, is that the user has to spend extra time pre-sorting the input data to reduce load imbalances. if the overall pair-align computation nodes are well balanced, performance will be greatly improved. the effect becomes dramatic when input sequences dominate the computation time, due to excessively long or short strings. this is necessary in the case of highly parallel file-swap systems where load balancing is a key speed-up feature for performance enhancement. physical ram addressing is preferred for small-to-medium-sized sequences, whereas the file-swap system is used for very large volume computations. to overcome the slow speed of the file memory computation, we designed an efficient load balancer, which uses a fast, intelligent scanning strategy to find sleeping computation nodes. based on the previous distribution characteristics of clustalw-mpi, we propose a dynamic scan-load balancing algorithm for efficient job-assignment of non-uniformly distributed pair-align computation nodes, which is specified to increase the speed of interprocessor communications. the original parallel version of clustalw-mpi uses a fixed-size chunk scheduler algorithm to distribute sequence pairs to each node. the main job of the master node in our system is to keep the slave nodes busy, as long as there is work to be done. that is, when a computation node completes its processing, it requests additional cue-sequence pairs from the master. this form of dynamic load-balancing continues until all of the sequences have been aligned. once the job is submitted, it can be monitored and controlled via clustalxeed main. new features in clustalxeed core new sequence editing options clustalxeed allows the user to change the order of sequences by simply cutting and pasting the sequence names. the sequence block grabber also provides a box-shaded area that enables the user to realign badly aligned sequences in a new window format, and to realign a small box region again. this option provides an independent task for the refinement of aligned sequences. the realignment range can be selected by simply clicking the mouse and dragging on the new sequence area. easy sequence finder enables a search for nucleic acids or proteins based on a partial sequence input. phylogenetic tree view option enhanced for the convenience of direct tree-drawing, treeview open source was embedded because some environments cannot read "unweighted pair group method with arithmetic mean" trees. this was a known problem in the previous versions of clustalx and clustalx. users can save the resulting tree image as a postscript {*.ps} file. clustalxeed supports standard truetype and postscript fonts, which may increase the resulting tree resolution when enlarged, especially in the case of a huge sequence data set. real-time in-process dialogue box a real-time in-process dialogue box was built to enable the user to quickly monitor the current status of the computation, the progression of the job, and information on the number of nodes involved in the calculation. neither clustalx nor x gives feedback on the computation status. when the msa is finished, the user can save all of the computation history to a {result.log} file. the used parameters are also saved in the working directory as a {result.par} file. this allows a user to view and edit tag information about all the individual batch sequence-alignment jobs. secondary structure prediction the gor iv and phd options were added, although their installation requires permission from the original developer. we do not provide this permission in clustalxeed. protein weight matrices clustalxeed provides more options for selecting protein-weight matrices. the former version of clustalx provides only three different protein-weight matrices: blosum pam and gonnet we added more than different types of protein-weight matrices for specifying scoring tables for the easy and accurate adjustment of sp score improvement. this allows the user to reduce or increase the multiple sequence alignment sensitivity.  clustalxeed allows the alignment of large numbers of nucleic acid or protein sequences. generally, the memory space requirement for the dynamic programming algorithm follows o. based on this, for over sequences, msa requires at least terabytes of memory just to construct a distance-tree matrix, regardless of sequence length. we evaluated our software using large volumes of real nucleic acid and protein data sets to assess its overall and detailed performance. we set up a typical × cpu amd opteron 64-bit cluster system with linux. the master node consists of a 10-terabyte hdd: 3ware raid adapter and gb dram, for a huge-tree matrix construction. each node is a dual-core opteron system with gb dram and a 1-terabyte hdd. to confirm the full sequence-loading and speed-up computation, almost six million sequences in an nt.gz file were first downloaded from ftp://ftp.ncbi.nih.gov/ blast/fasta. these dna sequences were divided into smaller data sets containing to sequences. with sequences as the first test set, which requires a nearly 8-terabyte file-managing environment for the msa job, the elapsed computation time was - to 6-times shorter than that without insta. the total execution time for the complete alignment of nucleic acid sequences by the disk-storage system was about 4700- s with insta, and 7500- s without insta. once the insta was built, the overall speed-up rate was directly increased with the added computation nodes. the total computation efficiency depends on the pair-align scoring stage. for a given number of sequences, the average speed of clustalxeed performance increased with the number of computation nodes. as a second performance test, we extracted from ncbi a data set comprised of protein sequences from the cytochrome p superfamily. the average length of the protein sequences was amino acids, with minimal length around aa and maximal length of aa. in total, × pair-wise sequence alignments are required to complete each sp score calculation. we randomly mixed all of these sequences and aligned them using the disk-storage system. figure summarizes the obtained execution times of different job-balancing conditions as a function of node numbers. when the load-balancing algorithm was applied, the execution time of clustalxeed was more than four times faster than the usual file-swap mode. the average speed-up for nodes was with insta and without insta. the observed speed-up difference was due to the efficient load-balancing of sparsely distributed sequence pairs, and it clearly demonstrated the success of the implemented load-balancing algorithm. we showed that there exists an optimal node number to be assigned to jobs for the effective usage of computation resources. it is important to determine what system size will result in the maximum speed-up. the speed-up rate, as a function of participating node numbers, was not linear, because there was implicit waiting time due to communication latency. all pairs of sequences in the clustalxeed main disk-storage are transferred to compute nodes, and the calculated pair scores are then returned to the master and are saved in the disk-storage distance matrix.  clustalw is the most widely used multiple sequence alignment program. the program uses a profile-based progressive alignment, with the alignment process divided into three steps: distance matrix/pair-wise alignment, guided tree generation, and progressive alignment. however, clustalw is not capable of estimating phylogenies and alignments for large data sets, because of slow computation times and limited memory usage. alternatives to clustalw include clustalx, a graphical user interface -based version of clustalw, and clustalw-mpi, a recently developed, parallel implementation version of clustalw. in the latter tool, all three required computation steps are performed in parallel to reduce the total computation time. for parallel job scheduling, clustalw-mpi uses a fixed-size chunk scheduler, which divides each job into uniform, fixed sizes. this method of batch job scheduling sometimes reduces the communication overhead required for a small and moderate number of sequences having very short lengths, such as ests. however, it is not always effective at balancing the workload required for a large number of sequences having unequal lengths. under these circumstances, the iteration for the next job scheduling is often delayed, which may result in high processor idle time. moreover, because clustalw-mpi uses a ram memory-storage mode, it has the inherent problem of a shortage of memory available for large-scale data sets. clustalxeed was designed to simultaneously address the dual needs of fast computation and large sequence data handling. core changes with significant strides in supporting disk-memory access capabilities and enhanced job scheduling can tackle this bottleneck by enhancing both storage capacity and speed. as mentioned previously, clustalw-mpi delivers fixed-size chunks to every compute node before the calculation. the batch scheduling mode needs high memory on each node, which may result in processor idling when the sequence lengths are not uniform. in contrast, the clustalxeed disk storage algorithm does not send all pair sequences to the computation nodes and instead master allocates the pair sequences individually to an appropriate node using a load-balancing idle node-seeking task algorithm to reduce the initial file transfer cost and slave node memory requirements. clustalxeed also provides a fixed size chunk algorithm in the memory-storage mode for alignment of small-to-medium-sized sequences. because clustalxeed was designed to work at the capacity of disk memory space, it has no inherent limitation on input sequence amounts. with a 64-bit compiler version, clustalxeed works with sequence arrays containing up to terabytes in disk-storage mode. in the disk memory operation, alignment speed was also improved by incorporating insta, which allocates or re-allocates tasks to idle nodes during pair alignment without the requirement for prior task information. in this way, insta determines from moment to moment which imbalanced nodes can be resolved immediately by allocating a new job. the main advantage of insta is its prompt scanning and decision-making without requiring decision complexity of rescheduling or reallocating tasks to resources at runtime, as occurs with static or other general dynamic load-balancing algorithms. while setting up a new sequence batch job, the user has the option to choose an appropriate alternate computing environment using the graphical menu option. other precise values of multiple sequence alignment tuning parameters can be set for each clustalxeed menu link individually. users can follow the progress of their alignment execution from the real-time in-process dialogue box. as indicated previously, the new parameter inputs, the easy-to-use realign option, the fully integrated graphical user interface, and the improved speed-up performance for very large volumes of sequence data may provide optimized computation of biological sequence alignments. clustalxeed demonstrates that the embedded insta is a simple and effective means to meet the high computational demands for massive biological-sequence alignments. moreover, large phylogenetic tree construction is becoming increasingly important, as vast amounts of biological sequences are used in the evolutionary and functional analysis of grouping organisms. clustalxeed provides a great opportunity for the discovery of large and reliable phylogenetic trees between interesting biological sequence data sets. based on the combination of new protein-weight matrices, encouraging results show that clustalxeed is one of most powerful msa tools available for the rapid construction of huge phylogenies. availability and requirements project name: clustalxeed. project home page: http://pchm.inje.ac.kr/clustalxeed. operating system: runs both on single and parallel linux-based clustal systems. programming language: c-language, message passing interface. other requirements: described in the project home page. more detailed installation instructions and a tutorial manual will also be available for download. license: clustalxeed is available in source code, without fee, for academic, non-profit uses. the program is distributed in the hope that it will become further improved and put to practical use. abbreviations hpc: high performance computing; gui: graphical user interface; msa: multiple sequence alignment; mpi: message passing interface; ram: random access memory; insta: idle node-seeking task algorithm; cpu: central processing unit; hdd: hard disk drive; i/o: input/output; malign: multiple alignment; sp: sum of pairs authors' contributions hj designed and wrote the software, with support from tk. both authors contributed to the writing of the manuscript. all authors read and approved the final manuscript. 
clustalxeed can now compute a large volume of biological sequence data sets, which were not tractable in any other parallel or single msa program. to solve the conventional memory-dependency problem, clustalxeed uses both physical random access memory and a distributed file-allocation system for distance matrix construction and pair-align computation. the computation efficiency of disk-storage system was markedly improved by implementing an efficient load-balancing algorithm, called "idle node-seeking task algorithm". we designed clustalxeed, a software system for multiple sequence alignment with incremental improvements over previous versions of the clustalx and clustalw-mpi software. 2) implementing an efficient task load-balancing algorithm, insta, which improves overall processing times for multiple sequence alignment with input sequences of non-uniform length. the new editing option and the graphical user interface provide ready access to a parallel-computing environment for users who seek fast and easy alignment of large dna and protein sequence sets. the commonly used multiple sequence alignment programs are still limited in their ability to handle very large amounts of sequences because the system lacks a scalable high-performance computing environment with a greatly extended data storage capacity. the primary advantage of clustalxeed over other multiple sequence alignment software is its ability to align a large family of protein or nucleic acid sequences.
 there is an increasing demand to assemble and align large-scale biological sequence data sets. the commonly used multiple sequence alignment programs are still limited in their ability to handle very large amounts of sequences because the system lacks a scalable high-performance computing environment with a greatly extended data storage capacity.  we designed clustalxeed, a software system for multiple sequence alignment with incremental improvements over previous versions of the clustalx and clustalw-mpi software. the primary advantage of clustalxeed over other multiple sequence alignment software is its ability to align a large family of protein or nucleic acid sequences. to solve the conventional memory-dependency problem, clustalxeed uses both physical random access memory and a distributed file-allocation system for distance matrix construction and pair-align computation. the computation efficiency of disk-storage system was markedly improved by implementing an efficient load-balancing algorithm, called "idle node-seeking task algorithm". the new editing option and the graphical user interface provide ready access to a parallel-computing environment for users who seek fast and easy alignment of large dna and protein sequence sets.  clustalxeed can now compute a large volume of biological sequence data sets, which were not tractable in any other parallel or single msa program. the main developments include: 1) the ability to tackle larger sequence alignment problems than possible with previous systems through markedly improved storage-handling capabilities. 2) implementing an efficient task load-balancing algorithm, insta, which improves overall processing times for multiple sequence alignment with input sequences of non-uniform length. 3) support for both single pc and distributed cluster systems. 