Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel Methods for Finding k-Mismatch Shortest Unique Substrings Using GPU.
| Content Provider | Semantic Scholar |
|---|---|
| Author | Schultz, Daniel W. Xu, Bojian |
| Copyright Year | 2019 |
| Abstract | k-mismatch shortest unique substring (SUS) queries have been proposed and studied very recently due to its useful applications in the subfield of computational biology. The k-mismatch SUS query over one given position of a string asks for a shortest substring that covers the given position and does not have a duplicate (within a Hamming distance of k) elsewhere in the string. The challenge in SUS query is to collectively find the SUS for every position of a massively long string in a both time- and space-efficient manner. All known efforts and results have been focused on improving and optimizing the time and space efficiency of SUS computation in the sequential CPU model. In this work, we propose the first parallel approach for k-mismatch SUS queries, particularly leveraging on the massive multi-threading architecture of the graphic processing unit (GPU) technology. Experimental study performed on a mid-end GPU using real-world biological data shows that our proposal is consistently faster than the fastest CPU solution by a factor of at least 6 for exact SUS queries ( k=0) and at least 23 for approximate SUS queries over DNA sequences ( ), while maintaining nearly the same peak memory usage as the most memory-efficient sequential CPU proposal. |
| File Format | PDF HTM / HTML |
| DOI | 10.1109/TCBB.2019.2935061 |
| PubMed reference number | 31425048 |
| Journal | Medline |
| Alternate Webpage(s) | http://penguin.ewu.edu/~bojianxu/publications/TCBB_isbra2018.pdf |
| Journal | IEEE/ACM transactions on computational biology and bioinformatics |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
