Improve Locality Sensitive Hashing for Genomic Similarity Detection

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

52 viewed

بهبود درهم‌ساز حساس به همسایگی برای تشخیص تشابه ژنومیک

52 Viewed

Type of Document: Ph.D. Dissertation
Language: Farsi
Document No: 58752 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Sharifi Zarchi, Ali
Abstract:
One of the common needs in bioinformatics research is the detection of shared features and similarities between read sequences or with a reference genome. For this purpose, both precise and heuristic algorithms are available. Generally, detecting similarities among various bioinformatics patterns is crucial for identifying and characterizing biological behaviors. One of the algorithms for estimating similarity between two large sets is locality-sensitive hashing (LSH), which has seen significant application over the past two decades. This algorithm has been utilized in bioinformatics across various areas, including genome assembly, alignment of reads to the reference genome, and metagenomic studies. In this research, we aim to enhance LSH for genomic similarity detection. To achieve this, we have introduced multi-metric locality-sensitive hashing and multi-metric MinHash. We further demonstrate that these concepts are firmly rooted in the fundamental principles of LSH. Finally, we have developed a tool based on these concepts that offers significantly higher accuracy compared to existing tools
Keywords:
Metagenomics ; MinHash ; Bisulfite Sequencing ; Genome Alignment ; Locality-Sensitive Hashing ; Multi-Metric

No TOC