Cargando…

FOGSAA: Fast Optimal Global Sequence Alignment Algorithm

In this article we propose a Fast Optimal Global Sequence Alignment Algorithm, FOGSAA, which aligns a pair of nucleotide/protein sequences faster than any optimal global alignment method including the widely used Needleman-Wunsch (NW) algorithm. FOGSAA is applicable for all types of sequences, with...

Descripción completa

Detalles Bibliográficos
Autores principales: Chakraborty, Angana, Bandyopadhyay, Sanghamitra
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Nature Publishing Group 2013
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3638164/
https://www.ncbi.nlm.nih.gov/pubmed/23624407
http://dx.doi.org/10.1038/srep01746
_version_ 1782475804628746240
author Chakraborty, Angana
Bandyopadhyay, Sanghamitra
author_facet Chakraborty, Angana
Bandyopadhyay, Sanghamitra
author_sort Chakraborty, Angana
collection PubMed
description In this article we propose a Fast Optimal Global Sequence Alignment Algorithm, FOGSAA, which aligns a pair of nucleotide/protein sequences faster than any optimal global alignment method including the widely used Needleman-Wunsch (NW) algorithm. FOGSAA is applicable for all types of sequences, with any scoring scheme, and with or without affine gap penalty. Compared to NW, FOGSAA achieves a time gain of (70–90)% for highly similar nucleotide sequences (> 80% similarity), and (54–70)% for sequences having (30–80)% similarity. For other sequences, it terminates with an approximate score. For protein sequences, the average time gain is between (25–40)%. Compared to three heuristic global alignment methods, the quality of alignment is improved by about 23%–53%. FOGSAA is, in general, suitable for aligning any two sequences defined over a finite alphabet set, where the quality of the global alignment is of supreme importance.
format Online
Article
Text
id pubmed-3638164
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher Nature Publishing Group
record_format MEDLINE/PubMed
spelling pubmed-36381642013-04-29 FOGSAA: Fast Optimal Global Sequence Alignment Algorithm Chakraborty, Angana Bandyopadhyay, Sanghamitra Sci Rep Article In this article we propose a Fast Optimal Global Sequence Alignment Algorithm, FOGSAA, which aligns a pair of nucleotide/protein sequences faster than any optimal global alignment method including the widely used Needleman-Wunsch (NW) algorithm. FOGSAA is applicable for all types of sequences, with any scoring scheme, and with or without affine gap penalty. Compared to NW, FOGSAA achieves a time gain of (70–90)% for highly similar nucleotide sequences (> 80% similarity), and (54–70)% for sequences having (30–80)% similarity. For other sequences, it terminates with an approximate score. For protein sequences, the average time gain is between (25–40)%. Compared to three heuristic global alignment methods, the quality of alignment is improved by about 23%–53%. FOGSAA is, in general, suitable for aligning any two sequences defined over a finite alphabet set, where the quality of the global alignment is of supreme importance. Nature Publishing Group 2013-04-29 /pmc/articles/PMC3638164/ /pubmed/23624407 http://dx.doi.org/10.1038/srep01746 Text en Copyright © 2013, Macmillan Publishers Limited. All rights reserved http://creativecommons.org/licenses/by-nc-nd/3.0/ This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/3.0/
spellingShingle Article
Chakraborty, Angana
Bandyopadhyay, Sanghamitra
FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title_full FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title_fullStr FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title_full_unstemmed FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title_short FOGSAA: Fast Optimal Global Sequence Alignment Algorithm
title_sort fogsaa: fast optimal global sequence alignment algorithm
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3638164/
https://www.ncbi.nlm.nih.gov/pubmed/23624407
http://dx.doi.org/10.1038/srep01746
work_keys_str_mv AT chakrabortyangana fogsaafastoptimalglobalsequencealignmentalgorithm
AT bandyopadhyaysanghamitra fogsaafastoptimalglobalsequencealignmentalgorithm