ABSTRACT
Most of the exact algorithms for biological sequence comparison obtain the optimal result by calculating dynamic programming (DP) matrices with quadratic time and space complexity. Fickett prunes the DP matrices by only computing values inside a band of size k, thus reducing time and space complexity to [Formula: see text]. Myers and Miller (MM) proposed a linear space algorithm that splits a sequence comparison into multiple comparisons of subsequences, using a divide-and-conquer approach. In this article, we propose a parallel strategy that combines the Fickett and MM algorithms, thus adding pruning capability to the MM algorithm. By using an appropriate Fickett band in each subsequence comparison, we can significantly reduce the number of cells computed in the DP matrices. Our strategy was integrated to stages 3 and 4 of CUDAlign, a state-of-the-art parallel tool for optimal biological sequence comparison, generating two implementations: Fickett-MM-4 and Fickett-MM-3-4. These implementations were used to compare real DNA sequences, reaching a speedup of 101.19 × in the 10 × 10 millions of base pairs comparison when compared with CUDAlign stages 3 and 4. In this case, the execution time was reduced from 71.42 to 0.7 seconds.
Subject(s)
Algorithms , Computational Biology/methods , Sequence Alignment/methods , Sequence Analysis/methodsABSTRACT
Paracoccidioides brasiliensis is the etiological agent of paracoccidioidomycosis, an endemic mycosis of Latin America. This fungus presents a dimorphic character; it grows as a mycelium at room temperature, but it is isolated as yeast from infected individuals. It is believed that the transition from mycelium to yeast is important for the infective process. The Functional and Differential Genome of Paracoccidioides brasiliensis Project--PbGenome Project was developed to study the infection process by analyzing expressed sequence tags--ESTs, isolated from both mycelial and yeast forms. The PbGenome Project was executed by a consortium that included 70 researchers (professors and students) from two sequencing laboratories of the midwest region of Brazil; this project produced 25,741 ESTs, 19,718 of which with sufficient quality to be analyzed. We describe the computational procedures used to receive process, analyze these ESTs, and help with their functional annotations; we also detail the services that were used for sequence data exploration. Various programs were compared for filtering and grouping the sequences, and they were adapted to a user-friendly interface. This system made the analysis of the differential transcriptome of P. brasiliensis possible.
