A rapid heuristic algorithm to solve the single individual haplotype assembly problem
The Haplotype Assembly is the computational process in which two distinct nucleotide sequences of chromosomes are reconstructed using the sequencing reads of an individual. The ability to identify haplotypes provides many benefits for future genomic-based studies to be conducted in many areas, such...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Amirkabir University of Technology
2023-12-01
|
| Series: | AUT Journal of Electrical Engineering |
| Subjects: | |
| Online Access: | https://eej.aut.ac.ir/article_5196_c206979ddc5b6231b7cfc699bfbdc0ba.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849434208439631872 |
|---|---|
| author | Melina Bagher Reza Karimzadeh Mehran Jahed Babak Hossein Khalaj |
| author_facet | Melina Bagher Reza Karimzadeh Mehran Jahed Babak Hossein Khalaj |
| author_sort | Melina Bagher |
| collection | DOAJ |
| description | The Haplotype Assembly is the computational process in which two distinct nucleotide sequences of chromosomes are reconstructed using the sequencing reads of an individual. The ability to identify haplotypes provides many benefits for future genomic-based studies to be conducted in many areas, such as drug design, population study, and disease diagnosis. Even though several approaches have been put out to achieve highly accurate haplotypes, the problem of quick and precise haplotype assembly remains a challenging task. Due to the enormous bulk of the high-throughput sequencing data, algorithm speed plays a crucial role in the possibility of haplotype assembly in the human genome dimension. This study introduces a heuristic technique that enables rapid haplotype reconstruction while maintaining respectable accuracy. Our approach is divided into two parts. In the first, a partial haplotype is created and enlarged over a number of iterations. We have employed a novel metric to assess the reconstructed haplotype's quality in each iteration to arrive at the optimal answer. The second stage of the algorithm involves refining the reconstructed haplotypes to increase their accuracy. The outcome reveals that the suggested approach is capable of reconstructing the haplotypes with an acceptable level of accuracy. In terms of speed, the performance of the algorithm surpasses the competing approaches, especially in the case of high-coverage sequencing data. |
| format | Article |
| id | doaj-art-a99786cac8394f8d87ff98bf52ea3d09 |
| institution | Kabale University |
| issn | 2588-2910 2588-2929 |
| language | English |
| publishDate | 2023-12-01 |
| publisher | Amirkabir University of Technology |
| record_format | Article |
| series | AUT Journal of Electrical Engineering |
| spelling | doaj-art-a99786cac8394f8d87ff98bf52ea3d092025-08-20T03:26:44ZengAmirkabir University of TechnologyAUT Journal of Electrical Engineering2588-29102588-29292023-12-0155219120610.22060/eej.2023.22434.55435196A rapid heuristic algorithm to solve the single individual haplotype assembly problemMelina Bagher0Reza Karimzadeh1Mehran Jahed2Babak Hossein Khalaj3Department of Electrical Engineering, Sharif University of Technology, Tehran, IranDepartment of Electrical Engineering, Sharif University of Technology, Tehran, IranDepartment of Electrical Engineering, Sharif University of Technology, Tehran, IranDepartment of Electrical Engineering, Sharif University of Technology, Tehran, IranThe Haplotype Assembly is the computational process in which two distinct nucleotide sequences of chromosomes are reconstructed using the sequencing reads of an individual. The ability to identify haplotypes provides many benefits for future genomic-based studies to be conducted in many areas, such as drug design, population study, and disease diagnosis. Even though several approaches have been put out to achieve highly accurate haplotypes, the problem of quick and precise haplotype assembly remains a challenging task. Due to the enormous bulk of the high-throughput sequencing data, algorithm speed plays a crucial role in the possibility of haplotype assembly in the human genome dimension. This study introduces a heuristic technique that enables rapid haplotype reconstruction while maintaining respectable accuracy. Our approach is divided into two parts. In the first, a partial haplotype is created and enlarged over a number of iterations. We have employed a novel metric to assess the reconstructed haplotype's quality in each iteration to arrive at the optimal answer. The second stage of the algorithm involves refining the reconstructed haplotypes to increase their accuracy. The outcome reveals that the suggested approach is capable of reconstructing the haplotypes with an acceptable level of accuracy. In terms of speed, the performance of the algorithm surpasses the competing approaches, especially in the case of high-coverage sequencing data.https://eej.aut.ac.ir/article_5196_c206979ddc5b6231b7cfc699bfbdc0ba.pdfhaplotype reconstructionsingle nucleotide polymorphismhaplotype assemblyfragmentsequencing |
| spellingShingle | Melina Bagher Reza Karimzadeh Mehran Jahed Babak Hossein Khalaj A rapid heuristic algorithm to solve the single individual haplotype assembly problem AUT Journal of Electrical Engineering haplotype reconstruction single nucleotide polymorphism haplotype assembly fragment sequencing |
| title | A rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| title_full | A rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| title_fullStr | A rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| title_full_unstemmed | A rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| title_short | A rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| title_sort | rapid heuristic algorithm to solve the single individual haplotype assembly problem |
| topic | haplotype reconstruction single nucleotide polymorphism haplotype assembly fragment sequencing |
| url | https://eej.aut.ac.ir/article_5196_c206979ddc5b6231b7cfc699bfbdc0ba.pdf |
| work_keys_str_mv | AT melinabagher arapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT rezakarimzadeh arapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT mehranjahed arapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT babakhosseinkhalaj arapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT melinabagher rapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT rezakarimzadeh rapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT mehranjahed rapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem AT babakhosseinkhalaj rapidheuristicalgorithmtosolvethesingleindividualhaplotypeassemblyproblem |