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...
Autores principales: | , |
---|---|
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 |