4 results
Now showing1 - 4 of 4
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing unitsBipartite graphs are used to model and represent many real-world problems in biological and physical sciences. Finding shortest paths in bipartite graphs is an important task and has numerous applications. Different dynamic programming based solutions to find the shortest paths exists which differ on complexity and structure of graph. The computational complexity of these algorithms is a major concern. This work formulates the parallel versions of Floyd-Warshall and Torgasin-Zimmermann algorithms to compute the shortest paths in bipartite graphs efficiently. These algorithms are mapped to graphics processing unit using tropical matrix product. The performance for different realizations and parameters are compared for Floyd-Warshall and Torgasin-Zimmermann algorithms. Parallel implementation of Torgasin-Zimmermann algorithm attained a speed-up factor of almost 274 when compared with serial Floyd-Warshall algorithm for random-generated undirected graphs.Publicationtype: Journal Article26 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Accelerating Viterbi algorithm on graphics processing unitsViterbi algorithm is used in different scientific applications including biological sequence alignment, speech recognition, and probabilistic inference. However, high computational complexity of the Viterbi algorithm is a major concern. Accelerating the Viterbi algorithm is important, especially when the number of states or the length of the sequences increase significantly. In this paper, a parallel solution to improve the performance of Viterbi algorithm is presented. This is achieved by formulating a matrix product based algorithm. This algorithm has been mapped to a NVIDIA graphics processing unit. The performance for different parameters and realizations are compared. The results depicts matrix product is not a viable option for small number of states. However, matrix product solution using shared memory for large number of states gains good performance when compared with the serial version.Publicationtype: Journal Article117 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Mapping dynamic programming algorithms on graphics processing unitsAlignment is the fundamental operation used to compare biological sequences. It also serves to identify regions of similarity that are eventually consequences of structural, functional, or evolutionary relationships. Today, the processing of sequences from large DNA or protein databases is a big challenge. Graphics Processing Units (GPUs) are based on a highly parallel, many-core streaming architecture and can be used to tackle the processing of large biological data. In the thesis, progressive alignment methods and their parallel implemenation by modern GPUs are studied. It turns out that wavefront and matrix-matrix product techniques can cope best with the data dependencies and so are highly appropriate for the implementation on a GPU. The performance of these methods is analyzed and the method with the highest speed-up is used to realize the alignment stage in the well-known software package ClustalW. Similar studies are made for the hidden Markov model. General principles and guidelines for GPU programming of matrix-based algorithms are discussed.Publicationtype: Doctoral Thesis915 1238 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Graphics card processing : accelerating profile-profile alignment© 2012 Versita Warsaw. Alignment is the fundamental operation in molecular biology for comparing biomolecular sequences. The most widely used method for aligning groups of alignments is based on the alignment of the profiles corresponding to the groups. We show that profile-profile alignment can be significantly speeded up by general purpose computing on a modern commodity graphics card. Wavefront and matrix-matrix product approaches for implementing profile-profile alignment onto graphics processor are analyzed. The average speed-up obtained is one order of magnitude even when overheads are considered. Thus the computational power of graphics cards can be exploited to develop improved solutions for multiple sequence alignment.Publicationtype: Journal ArticleScopus© Citations 1 301 292