{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:15:42Z","timestamp":1762298142295,"version":"3.40.4"},"reference-count":46,"publisher":"Wiley","issue":"13","license":[{"start":{"date-parts":[[2014,8,5]],"date-time":"2014-08-05T00:00:00Z","timestamp":1407196800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"crossref","award":["NSC-100-2221-E-126-007-MY3"],"award-info":[{"award-number":["NSC-100-2221-E-126-007-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2015,9,10]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>Constructing phylogenetic trees is of priority concern in computational biology, especially for developing biological taxonomies. As a conventional means of constructing phylogenetic trees, unweighted pair group method with arithmetic (UPGMA) is also an extensively adopted heuristic algorithm for constructing ultrametric trees (UT). Although the UT constructed by UPGMA is often not a true tree unless the molecular clock assumption holds, UT is still useful for the clocklike data. Moreover, UT has been successfully adopted in other problems, including orthologous\u2010domain classification and multiple sequence alignment. However, previous implementations of the UPGMA method have a limited ability to handle large taxa sets efficiently. This work describes a novel graphics processing unit (GPU)\u2010UPGMA approach, capable of providing rapid construction of extremely large datasets for biologists. Experimental results indicate that the proposed GPU\u2010UPGMA approach achieves an approximately 95\u00d7 speedup ratio on NVIDIA Tesla C2050 GPU over the implementation with 2.13\u2009GHz CPU. The developed techniques in GPU\u2010UPGMA also can be applied to solve the classification problem for large data set with more than tens of thousands items in the future.Copyright \u00a9 2014 John Wiley &amp; Sons, Ltd.<\/jats:p>","DOI":"10.1002\/cpe.3355","type":"journal-article","created":{"date-parts":[[2014,8,5]],"date-time":"2014-08-05T23:43:06Z","timestamp":1407282186000},"page":"3403-3414","source":"Crossref","is-referenced-by-count":11,"title":["GPU\u2010UPGMA: high\u2010performance computing for UPGMA algorithm based on graphics processing units"],"prefix":"10.1002","volume":"27","author":[{"given":"Yu\u2010Shiang","family":"Lin","sequence":"first","affiliation":[{"name":"Department of Computer Science National Tsing Hua University No. 101, Section 2, Kuang\u2010Fu Road Hsinchu City 30013 Taiwan"}]},{"given":"Chun\u2010Yuan","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering Chang Gung University No. 259, Sanmin Rd., Guishan Township Taoyuan City 33302 Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8906-9367","authenticated-orcid":false,"given":"Che\u2010Lun","family":"Hung","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communication Engineering Providence University No. 200, Sec. 7, Taiwan Boulevard, Shalu Dist. Taichung City 43301 Taiwan"}]},{"given":"Yeh\u2010Ching","family":"Chung","sequence":"additional","affiliation":[{"name":"Department of Computer Science National Tsing Hua University No. 101, Section 2, Kuang\u2010Fu Road Hsinchu City 30013 Taiwan"}]},{"given":"Kual\u2010Zheng","family":"Lee","sequence":"additional","affiliation":[{"name":"Information and Communications Research Laboratories Industrial Technology Rearch Institute No. 195, Sec. 4, Chung Hsing Rd., Chutung Hsinchu City 31040 Taiwan"}]}],"member":"311","published-online":{"date-parts":[[2014,8,5]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ge.22.120188.002513"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"volume-title":"Fundamentals of Molecular Evolution","year":"1991","author":"Li WH","key":"e_1_2_8_4_1"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-2734-4.50017-6"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(82)90027-X"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403001"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406041"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188585"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90090-7"},{"volume-title":"Numerical Taxonomy","year":"1973","author":"Sneath PHA","key":"e_1_2_8_11_1"},{"key":"e_1_2_8_12_1","first-page":"406","article-title":"The neighbor\u2010joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou N","year":"1987","journal-title":"Molecular Biology and Evolution"},{"key":"e_1_2_8_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a026281"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/155.3.1429"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkj448"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-1119(88)90330-7"},{"key":"e_1_2_8_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh340"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkl091"},{"issue":"6","key":"e_1_2_8_19_1","first-page":"729","article-title":"A note on the neighbor\u2010joining algorithm of Saitou and Nei","volume":"5","author":"Studier JA","year":"1988","journal-title":"Molecular Biology and Evolution"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg192"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.22.4673"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2006.05.001"},{"key":"e_1_2_8_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.04.008"},{"key":"e_1_2_8_24_1","unstructured":"OpenCL:https:\/\/www.khronos.org\/opencl\/[accessed on 2013]."},{"key":"e_1_2_8_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"e_1_2_8_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_2_8_27_1","doi-asserted-by":"crossref","unstructured":"LiuY SchmidtB MaskellDL.MSA\u2010CUDA: multiple sequence alignment on graphics processing units with CUDA.Proceedings of ASAP 2009;121\u2013128.","DOI":"10.1109\/ASAP.2009.14"},{"key":"e_1_2_8_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.10.009"},{"key":"e_1_2_8_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.33"},{"key":"e_1_2_8_30_1","doi-asserted-by":"crossref","unstructured":"LiuW SchmidtB LiuY VossG Mu\u00a8ller\u2010WittigW.Mapping of BLASTP algorithm onto GPU clusters.Proceedings of ICPADS 2011;236\u2013243.","DOI":"10.1109\/ICPADS.2011.79"},{"key":"e_1_2_8_31_1","unstructured":"LiuY SchmidtB MaskellDL.Parallel reconstruction of neighbor\u2010joining trees for large multiple sequence alignments using CUDA.Proceedings of IPDPS 2009;23\u201329."},{"key":"e_1_2_8_32_1","doi-asserted-by":"crossref","unstructured":"LiuP PaulK.A coarse\u2010grained reconfigurable processor for sequencing and phylogenetic algorithms in bioinformatics.Proceedings of ReConFig 2011;190\u2013197.","DOI":"10.1109\/ReConFig.2011.1"},{"key":"e_1_2_8_33_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-S2-S10"},{"key":"e_1_2_8_34_1","doi-asserted-by":"crossref","unstructured":"StriemerGM AkogluA.Sequence alignment with GPU: performance and design challenges.Proceedings of IPDPS 2009;1\u201310.","DOI":"10.1109\/IPDPS.2009.5161066"},{"key":"e_1_2_8_35_1","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0500-2-73"},{"key":"e_1_2_8_36_1","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0500-3-93"},{"key":"e_1_2_8_37_1","doi-asserted-by":"crossref","unstructured":"SandesFDO MeloACMAD.CUDAlign: using GPU to accelerate the comparison of megabase genomic sequences.Proceedings of PPOPP 2010;137\u2013146.","DOI":"10.1145\/1837853.1693473"},{"key":"e_1_2_8_38_1","doi-asserted-by":"crossref","unstructured":"SandesFDO MeloACMAD.Smith\u2013Waterman alignment of huge sequences with GPU in linear space.Proceedings of IPDPS 2011;1199\u20131211.","DOI":"10.1109\/IPDPS.2011.114"},{"key":"e_1_2_8_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2010.02.009"},{"key":"e_1_2_8_40_1","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/721738"},{"key":"e_1_2_8_41_1","unstructured":"SreesaA DavisJP.Custom computing for phylogenetics: exploring the solution space for UPGMA.Proceedings of FCCM 2004."},{"key":"e_1_2_8_42_1","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal R","year":"1958","journal-title":"University of Kansas Science Bulletin"},{"key":"e_1_2_8_43_1","unstructured":"RogerD AssarssonU HolzschuchN.Efficient stream reduction on the GPU.Proceedings of GPGPU 2007."},{"key":"e_1_2_8_44_1","unstructured":"HarrisM.Optimizing parallel reduction in CUDA. Nvidia Tech Rep 2007."},{"key":"e_1_2_8_45_1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.5815\/ijmecs.2011.04.08","article-title":"Design and implementation of GPU\u2010based Prim's algorithm","volume":"4","author":"Wang W","year":"2011","journal-title":"I.J.Modern Education and Computer Science"},{"key":"e_1_2_8_46_1","unstructured":"QT:http:\/\/qt\u2010project.org[accessed on 2013]."},{"key":"e_1_2_8_47_1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msr121"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.3355","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.3355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T02:28:18Z","timestamp":1746325698000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.3355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,5]]},"references-count":46,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2015,9,10]]}},"alternative-id":["10.1002\/cpe.3355"],"URL":"https:\/\/doi.org\/10.1002\/cpe.3355","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2014,8,5]]}}}