{"id":{"repo_id":"colostate","oai_identifier":"oai:mountainscholar.org:10217/232479"},"canonical_url":"https://search.dev.ndltd.org/etd/colostate/oai:mountainscholar.org:10217/232479","repository":{"repo_id":"colostate","name":"Colorado State University","base_url":"https://api.mountainscholar.org/server/oai/request"},"display":{"title":"A GPU accelerated RNA-RNA interaction program","abstract":"RNA-RNA interaction (RRI) is important in processes like gene regulation, and is known to play roles in diseases including cancer and Alzheimer's. Large RRI computations run for days, weeks or even months, because the algorithms have time and space complexity of, respectively, O(N3M3) and O(N2M2), for sequences length N and M, and there is a need for high-throughput RRI tools. GPU parallelization of such algorithms is a challenge. We first show that the most computationally expensive part of base pair maximization (BPM) algorithms comprises O(N3) instances of upper banded tropical matrix products. We develop the first GPU library for this attaining close to theoretical machine peak (TMP). We next optimize other (fifth degree polynomial) terms in the computation and develop the first GPU implementation of the complete BPMax algorithm. We attain 12% of GPU TMP, a significant speedup over the original parallel CPU implementation, which attains less than 1% of CPU TMP. We also perform a large scale study of three small viral RNAs, hypothesized to be relevant to COVID-19.","abstract_html":"RNA-RNA interaction (RRI) is important in processes like gene regulation, and is known to play roles in diseases including cancer and Alzheimer's. Large RRI computations run for days, weeks or even months, because the algorithms have time and space complexity of, respectively, O(N3M3) and O(N2M2), for sequences length N and M, and there is a need for high-throughput RRI tools. GPU parallelization of such algorithms is a challenge. We first show that the most computationally expensive part of base pair maximization (BPM) algorithms comprises O(N3) instances of upper banded tropical matrix products. We develop the first GPU library for this attaining close to theoretical machine peak (TMP). We next optimize other (fifth degree polynomial) terms in the computation and develop the first GPU implementation of the complete BPMax algorithm. We attain 12% of GPU TMP, a significant speedup over the original parallel CPU implementation, which attains less than 1% of CPU TMP. We also perform a large scale study of three small viral RNAs, hypothesized to be relevant to COVID-19.","abstract_has_math":false,"creators":["Gildemaster, Brandon, author","Rajopadhye, Sanjay, advisor","Chitsaz, Hamidreza, committee member","Abdo, Zaid, committee member"],"institution":"Colorado State University. Libraries","degree_name":"Master of Science (M.S.)","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-07-27T19:13:11Z","subjects":[],"languages":["eng","English"],"rights":["Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.25675/3.02465"],"render_values":[{"text":"https://doi.org/10.25675/3.02465","href":"https://doi.org/10.25675/3.02465","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10217/232479","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Gildemaster, Brandon, author","Rajopadhye, Sanjay, advisor","Chitsaz, Hamidreza, committee member","Abdo, Zaid, committee member"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-06-07T10:19:41Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-06-07T10:19:41Z"]},{"key":"dc:date.issued","label":"Date","values":["2021"]},{"key":"dc:publisher","label":"Institution","values":["Colorado State University. Libraries"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Colorado State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Gildemaster_colostate_0053N_16445.pdf"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10217/232479","https://doi.org/10.25675/3.02465"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["RNA-RNA interaction (RRI) is important in processes like gene regulation, and is known to play roles in diseases including cancer and Alzheimer's. Large RRI computations run for days, weeks or even months, because the algorithms have time and space complexity of, respectively, O(N3M3) and O(N2M2), for sequences length N and M, and there is a need for high-throughput RRI tools. GPU parallelization of such algorithms is a challenge. We first show that the most computationally expensive part of base pair maximization (BPM) algorithms comprises O(N3) instances of upper banded tropical matrix products. We develop the first GPU library for this attaining close to theoretical machine peak (TMP). We next optimize other (fifth degree polynomial) terms in the computation and develop the first GPU implementation of the complete BPMax algorithm. We attain 12% of GPU TMP, a significant speedup over the original parallel CPU implementation, which attains less than 1% of CPU TMP. We also perform a large scale study of three small viral RNAs, hypothesized to be relevant to COVID-19."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["born digital","masters theses"]},{"key":"dc:title","label":"Title","values":["A GPU accelerated RNA-RNA interaction program"]}]}],"canonical_facts":{"dc:creator":["Gildemaster, Brandon, author","Rajopadhye, Sanjay, advisor","Chitsaz, Hamidreza, committee member","Abdo, Zaid, committee member"],"dc:date.accessioned":["2021-06-07T10:19:41Z"],"dc:date.available":["2021-06-07T10:19:41Z"],"dc:date.issued":["2021"],"dc:description.abstract":["RNA-RNA interaction (RRI) is important in processes like gene regulation, and is known to play roles in diseases including cancer and Alzheimer's. Large RRI computations run for days, weeks or even months, because the algorithms have time and space complexity of, respectively, O(N3M3) and O(N2M2), for sequences length N and M, and there is a need for high-throughput RRI tools. GPU parallelization of such algorithms is a challenge. We first show that the most computationally expensive part of base pair maximization (BPM) algorithms comprises O(N3) instances of upper banded tropical matrix products. We develop the first GPU library for this attaining close to theoretical machine peak (TMP). We next optimize other (fifth degree polynomial) terms in the computation and develop the first GPU implementation of the complete BPMax algorithm. We attain 12% of GPU TMP, a significant speedup over the original parallel CPU implementation, which attains less than 1% of CPU TMP. We also perform a large scale study of three small viral RNAs, hypothesized to be relevant to COVID-19."],"dc:format.medium":["born digital","masters theses"],"dc:identifier":["Gildemaster_colostate_0053N_16445.pdf"],"dc:identifier.uri":["https://hdl.handle.net/10217/232479","https://doi.org/10.25675/3.02465"],"dc:language":["English"],"dc:language.iso":["eng"],"dc:publisher":["Colorado State University. Libraries"],"dc:rights":["Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright."],"dc:title":["A GPU accelerated RNA-RNA interaction program"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science (M.S.)"],"thesis:institution_name":["Colorado State University"]},"updated_at":"2026-07-27T19:13:11Z"}