부산대학교 도서관

The field of bioinformatics is an extensive and rich area of research. Most efforts today focus on genetic sequence alignment which is needed to be performed in almost all genomic studies. It is the positioning of two gene sequences (Deoxyribonucleic Acid (DNA), Ribonucleic acid (RNA), peptide sequence, and so on) such that their similar regions are matched. This alignment is then scored by taking weighted sum of the matches, mismatches, and gaps (indels). The alignment is considered to be significant if the score satisfies a certain threshold. Over the years, vast research has been conducted to tackle the enormous problem of alignment of human genetic sequences efficiently for the purpose of newborn genetic screening and early detection of genetic disorders. The human DNA, which is over 3 billion base pairs long, presents a challenge to these methods as they attempt to run in an acceptable amount of time and memory space. This paper presents an overview of the most prominent algorithms along with their asymptotic analysis. It is our hope that a comparative view of the various methods shall help to determine which one or more of them can be considered for further betterment.