دانلود مقاله ISI انگلیسی شماره 79136
ترجمه فارسی عنوان مقاله

یک الگوریتم خوشه بندی سلسله مراتبی سریع برای مجموعه داده توالی پروتئین مقیاس بزرگ

عنوان انگلیسی
A fast hierarchical clustering algorithm for large-scale protein sequence data sets
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
79136 2014 8 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers in Biology and Medicine, Volume 48, 1 May 2014, Pages 94–101

ترجمه کلمات کلیدی
خوشه بندی دنباله پروتئین؛ خوشه بندی مارکوف؛ فرآیندهای مارکف؛ محاسبات کارآمد؛ ماتریس پراکنده
کلمات کلیدی انگلیسی
Protein sequence clustering; Markov clustering; Markov processes; Efficient computing; Sparse matrix
پیش نمایش مقاله
پیش نمایش مقاله  یک الگوریتم خوشه بندی سلسله مراتبی سریع برای مجموعه داده توالی پروتئین مقیاس بزرگ

چکیده انگلیسی

TRIBE-MCL is a Markov clustering algorithm that operates on a graph built from pairwise similarity information of the input data. Edge weights stored in the stochastic similarity matrix are alternately fed to the two main operations, inflation and expansion, and are normalized in each main loop to maintain the probabilistic constraint. In this paper we propose an efficient implementation of the TRIBE-MCL clustering algorithm, suitable for fast and accurate grouping of protein sequences. A modified sparse matrix structure is introduced that can efficiently handle most operations of the main loop. Taking advantage of the symmetry of the similarity matrix, a fast matrix squaring formula is also introduced to facilitate the time consuming expansion. The proposed algorithm was tested on protein sequence databases like SCOP95. In terms of efficiency, the proposed solution improves execution speed by two orders of magnitude, compared to recently published efficient solutions, reducing the total runtime well below 1 min in the case of the 11,944 proteins of SCOP95. This improvement in computation time is reached without losing anything from the partition quality. Convergence is generally reached in approximately 50 iterations. The efficient execution enabled us to perform a thorough evaluation of classification results and to formulate recommendations regarding the choice of the algorithm׳s parameter values.