SHsearch. A Method for Fast Remote Homology Detection

Noha Yousri

ISBN 10: 3668534497 / ISBN 13: 9783668534490

Published by GRIN Verlag, 2017

About this Item

Druck auf Anfrage Neuware - Printed after ordering - Master's Thesis from the year 2014 in the subject Mathematics - Statistics, grade: 3.8, , language: English, abstract: Remote homology detection is the problem of detecting homology in cases of low sequence similarity. It is a hard computational problem with no approach that works well in all cases. Methods based on profile hidden Markov models (HMM) often exhibit relatively higher sensitivity for detecting remote homologies than commonly used approaches. However, calculating similarity scores in profile HMM methods is computationally intensive as they use dynamic programming algorithms. In this paper, we introduce SHsearch: a new method for remote protein homology detection. Our method is implemented as a modification of HHsearch: a remote protein homology detection method based on comparing two profile HMMs. The motivation for modification was to reduce the run time of HHsearch significantly with minimal sensitivity loss. SHsearch focuses on comparing the important submodels of the query and database HMMs instead of comparing the complete models. Hence, SHsearch achieves a significant speedup over HHsearch with minimal loss in sensitivity. On S C O P 1.63, SHsearch achieved 88x speedup with 8.2% loss in sensitivity with respect to HHsearch at an error rate of 10%, which is deemed to be an acceptable tradeoff.

Seller Inventory # 9783668534490

Bibliographic Details

• Title: SHsearch. A Method for Fast Remote Homology Detection
• Publisher: GRIN Verlag
• Publication Date: 2017
• Language: English
• ISBN 10: 3668534497
• ISBN 13: 9783668534490
• Binding: Taschenbuch
• Condition: Neu
• Dimensions: 297W x 210H x 3D millimeters 297 millimeters width by 210 millimeters height by 3 millimeters depth
• Weight: 113 grams

About this title

Synopsis

Master's Thesis from the year 2014 in the subject Mathematics - Statistics, grade: 3.8, language: English, abstract: Remote homology detection is the problem of detecting homology in cases of low sequence similarity. It is a hard computational problem with no approach that works well in all cases. Methods based on profile hidden Markov models (HMM) often exhibit relatively higher sensitivity for detecting remote homologies than commonly used approaches. However, calculating similarity scores in profile HMM methods is computationally intensive as they use dynamic programming algorithms. In this paper, we introduce SHsearch: a new method for remote protein homology detection. Our method is implemented as a modification of HHsearch: a remote protein homology detection method based on comparing two profile HMMs. The motivation for modification was to reduce the run time of HHsearch significantly with minimal sensitivity loss. SHsearch focuses on comparing the important submodels of the query and database HMMs instead of comparing the complete models. Hence, SHsearch achieves a significant speedup over HHsearch with minimal loss in sensitivity. On S C O P 1.63, SHsearch achieved 88x speedup with 8.2% loss in sensitivity with respect to HHsearch at an error rate of 10%, which is deemed to be an acceptable tradeoff.