similarity searching is an essential part of sequence analysis and searching public sequence databases to gain more information about a sequence is one of the tasks carried out most frequently in bioinformatics .
web services for database homology searches are provided at   by the national center for biotechnology information ( ncbi ) in the united states using the ncbi blast program ( 1 ) , and at   by the european bioinformatics institute ( ebi ) by using the ncbi blast program as well as the fasta ( 2 ) and the wu - blast ( gish 19962004 ; ) programs .
paralign is an alternative to the services provided by the ncbi , ebi and others .
the paralign service employs two different very sensitive algorithms that enable the identification of similarities that may pass undetected by the algorithms used by the other services .
as the service is running on a powerful computer cluster , searches are carried out at a high speed challenging that of other services .
the service is most useful for the identification of both nucleotide and amino acid database sequences that have significant , but possibly limited , similarity to the query sequence .
it is especially useful for the detection of remote protein homologs in cases where no other protein family members are known .
sensitive nucleotide sequence comparisons are useful for the detection of unwanted cross - hybridization loci of sirnas , microarray probes or pcr primers , or when looking for subtle similarities between nucleotide sequences , e.g. non - coding rna sequences .
the search form is located at   where the query sequence is entered and the database selected ( figure 1 ) .
one may choose from three different types of searches : ( i ) amino acid query sequence against any type of database , ( ii ) translated nucleotide query sequence against any type of database , or ( iii ) a direct comparison of a nucleotide query sequence against a nucleotide sequence database .
the maximum number of hits , alignments and suboptimal alignments that are to be shown , as well as the search algorithm , the e - value range and the scoring parameters ( score matrix and gap penalties ) may be selected .
when the search is completed , information about the query , database and search parameters will be shown together with a graphical overview of the hits , a list of hits ( with hypertext links to the alignments below ) and alignments ( with hypertext links to the corresponding ncbi entrez entries ) ( figure 2 ) .
the paralign software implements two search methods : ( i ) the accelerated smith  waterman method ( 3 ) and ( ii ) the heuristic paralign method ( 4 ) . to achieve speed , both methods exploit parallel computing technology , as described in more detail below .
waterman algorithm ( 5 ) accelerated with the parallel computing technology to achieve a speed more than six times higher than the implementation in ssearch ( 6 ) or similar software .
the paralign method is based on a search algorithm that is designed specifically with the parallel computing technology in mind . despite being a heuristic algorithm similar to ncbi blast in speed ( 1 ) ,
its sensitivity is similar to that of searches based on the smith  waterman algorithm . for ungapped alignments ,
the alignment scores calculated by the paralign algorithm are identical to those of the smith  waterman algorithm .
the software and service makes use of the parallel computing at several levels . 
 first level : both methods implemented in paralign employ parallel computing technology known as multimedia technology ( mmx / sse , altivec ) or single - instruction multiple - data ( simd ) technology to gain high speed .
this type of technology was originally designed for rapid processing of images , video and sound , and allows the microprocessor to carry out many operations on small numbers in parallel , instead of one single operation on a large number at a time . despite being available in most modern processors , the technology is rarely used by other bioinformatics software , except for a recent implementation of the hmmer software ( 7 ) using altivec ( ) . in paralign
, this technology is used to process the score values of several cells in the alignment matrix in parallel.second level : on symmetric multiprocessing ( smp ) computers having several microprocessors with shared common memory , multiple threads of the paralign program can run concurrently and search through different parts of the sequence database .
these threads are implemented using the standard posix threads ( pthreads).third level : clusters of multiple computing nodes connected together through a network may run one or more instances of paralign on each node that searches through different parts of the sequence database .
the communication between the nodes is implemented using the message - passing interface ( mpi ) standard , as implemented in the mpich ( ) or other packages .
the cluster powering the paralign service consists of 33 nodes with 2 intel xeon 2.4 ghz microprocessors and 2 gb ram each .
the nodes are running the red hat enterprise linux 3.0 workstation operating system , and are connected using gigabit ethernet switches .
first level : both methods implemented in paralign employ parallel computing technology known as multimedia technology ( mmx / sse , altivec ) or single - instruction multiple - data ( simd ) technology to gain high speed .
this type of technology was originally designed for rapid processing of images , video and sound , and allows the microprocessor to carry out many operations on small numbers in parallel , instead of one single operation on a large number at a time . despite being available in most modern processors , the technology is rarely used by other bioinformatics software , except for a recent implementation of the hmmer software ( 7 ) using altivec ( ) . in paralign
, this technology is used to process the score values of several cells in the alignment matrix in parallel .
second level : on symmetric multiprocessing ( smp ) computers having several microprocessors with shared common memory , multiple threads of the paralign program can run concurrently and search through different parts of the sequence database .
third level : clusters of multiple computing nodes connected together through a network may run one or more instances of paralign on each node that searches through different parts of the sequence database . the communication between the nodes is implemented using the message - passing interface ( mpi ) standard , as implemented in the mpich ( ) or other packages .
the cluster powering the paralign service consists of 33 nodes with 2 intel xeon 2.4 ghz microprocessors and 2 gb ram each .
the nodes are running the red hat enterprise linux 3.0 workstation operating system , and are connected using gigabit ethernet switches .
the common public databases provided by the ncbi are downloaded weekly and made available for searches .
databases are processed and stored in the same format as used by the ncbi blast ( 1 ) , making it easy to use the same databases for both programs .
the databases are distributed to the local hard disks on all nodes in the cluster .
the user submits search requests using the search form at   by entering a query sequence and selecting a database and appropriate search parameters .
the web server will process the request by running a submission script that checks the input .
if the input is ok , a search is submitted to a scheduling system using the torque resource manager ( ) , which is based on pbs .
if not , the user is presented with the information on the status of the search , including the position in the queue , whether the search is running , expected time of finishing , etc .
when results are ready , they are presented to the user . when a search is scheduled to be run on the cluster ,
the mpi system will start paralign on a selected number of nodes in the cluster .
the results from each node are collected by the first node , which puts them together to a final result .
the system is designed so that multiple searches in the same database will usually result in the same node searching through exactly the same part of the database .
this part of the database will usually be automatically cached in ram by the operating system the first time it is read from the local hard disk , making subsequent searches go faster because they will require little , if any , disk access . to get an impression of the total time used by the system from submission to results
p22134 ) of 296 amino acids as a query sequence against different databases using default search parameters . searching the ncbi non - redundant ( nr ) protein database containing a total of 790 million amino acids took 15 s using the paralign algorithm and 30 s using the accelerated smith 
a search in the human expressed sequence tag ( est ) database ( translated ) containing 3200 million nucleotides took 30 s using the paralign algorithm and 70 s using the accelerated smith 
stand - alone executables are available free of charge for academic use , while commercial use requires a paid license from the company sencel bioinformatics as ( ) . the stand - alone software is available for five different computing platforms : linux on i386 , linux on itanium , hp - ux on itanium , macos on powerpc and tru64 unix on alpha .
the software , as well as additional information about it , is available from the company 's website .
if the web service is used in any published work , please cite this paper .
alternatively , the papers describing the methods used may be cited : the accelerated smith  waterman algorithm ( 3 ) and/or the paralign algorithm ( 4 ) .
in particular , we would like to improve the web interface and the presentation of the results .
we have also planned a number of improvements to the stand - alone program , including versions for other computer architectures .
the paralign home page at   contains the search form where the query sequence is entered and the database and the search parameters are selected .
the search results include a graphical overview of the hits , a list of matches and the sequence alignments . in the graphical overview ,
the position of the matches relative to the query sequence is indicated with lines coloured according to the e - value of the alignment .
the data flow for distributed searches on the computer cluster is illustrated in this diagram .
database sequences are loaded directly from a file server into memory on each node . the query sequence and
the search parameters are transferred from the user , via the web server and queuing system to the nodes .
search results from each node are collected by the first node which then generates the final output that is presented to the user .
 paralign is a rapid and sensitive similarity search tool for the identification of distantly related sequences in both nucleotide and amino acid sequence databases . 
 two algorithms are implemented , accelerated smith  waterman and paralign . 
 the paralign algorithm is similar to smith  waterman in sensitivity , while as quick as blast for protein searches . 
 a form of parallel computing technology known as multimedia technology that is available in modern processors , but rarely used by other bioinformatics software , has been exploited to achieve the high speed . 
 the software is also designed to run efficiently on computer clusters using the message - passing interface standard . 
 a public search service powered by a large computer cluster has been set - up and is freely available at , where the major public databases can be searched . 
 the software can also be downloaded free of charge for academic use . 
INTRODUCTION
SEARCH METHODS
PARALLEL COMPUTING
PROCESSING OF SEARCH REQUESTS
AVAILABILITY
Figures and Tables