Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment

BACKGROUND: Multiple sequence alignment (MSA) is a crucial step in many molecular analyses and many MSA tools have been developed. Most of them use a greedy approach to construct a first alignment that is then refined by optimizing the sum of pair score (SP-score). The SP-score estimation is thus a...

Descripción completa

Detalles Bibliográficos
Autor principal: Ranwez, Vincent
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2016
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4978502/
https://www.ncbi.nlm.nih.gov/pubmed/27505054
http://dx.doi.org/10.1371/journal.pone.0160043
_version_ 1782447185513676800
author Ranwez, Vincent
author_facet Ranwez, Vincent
author_sort Ranwez, Vincent
collection PubMed
description BACKGROUND: Multiple sequence alignment (MSA) is a crucial step in many molecular analyses and many MSA tools have been developed. Most of them use a greedy approach to construct a first alignment that is then refined by optimizing the sum of pair score (SP-score). The SP-score estimation is thus a bottleneck for most MSA tools since it is repeatedly required and is time consuming. RESULTS: Given an alignment of n sequences and L sites, I introduce here optimized solutions reaching O(nL) time complexity for affine gap cost, instead of O(n(2)L), which are easy to implement.
format Online
Article
Text
id pubmed-4978502
institution National Center for Biotechnology Information
language English
publishDate 2016
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-49785022016-08-25 Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment Ranwez, Vincent PLoS One Research Article BACKGROUND: Multiple sequence alignment (MSA) is a crucial step in many molecular analyses and many MSA tools have been developed. Most of them use a greedy approach to construct a first alignment that is then refined by optimizing the sum of pair score (SP-score). The SP-score estimation is thus a bottleneck for most MSA tools since it is repeatedly required and is time consuming. RESULTS: Given an alignment of n sequences and L sites, I introduce here optimized solutions reaching O(nL) time complexity for affine gap cost, instead of O(n(2)L), which are easy to implement. Public Library of Science 2016-08-09 /pmc/articles/PMC4978502/ /pubmed/27505054 http://dx.doi.org/10.1371/journal.pone.0160043 Text en © 2016 Vincent Ranwez http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Ranwez, Vincent
Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title_full Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title_fullStr Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title_full_unstemmed Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title_short Two Simple and Efficient Algorithms to Compute the SP-Score Objective Function of a Multiple Sequence Alignment
title_sort two simple and efficient algorithms to compute the sp-score objective function of a multiple sequence alignment
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4978502/
https://www.ncbi.nlm.nih.gov/pubmed/27505054
http://dx.doi.org/10.1371/journal.pone.0160043
work_keys_str_mv AT ranwezvincent twosimpleandefficientalgorithmstocomputethespscoreobjectivefunctionofamultiplesequencealignment

Ejemplares similares