A parallel Expressed Sequence Tag (EST) clustering program

This paper describes the Ulcluster software tool, which partitions Expressed Sequence Tag (EST) sequences and other genetic sequences into "clusters" based on sequence similarity. Ideally, each cluster will contain sequences that all represent the same gene. If a naive approach such as an NxN comparison (N is the number of sequences input) is taken, the problem is only feasible for very small data sets. Ulcluster has been developed over the course of four years to solve this problem efficiently and accurately for large data sets consisting of tens or hundreds of thousands of EST sequences. The latest version of the application has been parallelized using the MPI (message passing interface) standard. Both the computation and memory requirements of the program can be distributed among multiple (possibly distributed) UNIX processes.