1 Search Results for "Rozante, Luiz C."

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.40

Algorithms for Normalized Multiple Sequence Alignments

Authors: Eloi Araujo, Luiz C. Rozante, Diego P. Rubert, and Fábio V. Martinez

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

Sequence alignment supports numerous tasks in bioinformatics, natural language processing, pattern recognition, social sciences, and other fields. While the alignment of two sequences may be performed swiftly in many applications, the simultaneous alignment of multiple sequences proved to be naturally more intricate. Although most multiple sequence alignment (MSA) formulations are NP-hard, several approaches have been developed, as they can outperform pairwise alignment methods or are necessary for some applications. Taking into account not only similarities but also the lengths of the compared sequences (i.e. normalization) can provide better alignment results than both unnormalized or post-normalized approaches. While some normalized methods have been developed for pairwise sequence alignment, none have been proposed for MSA. This work is a first effort towards the development of normalized methods for MSA. We discuss multiple aspects of normalized multiple sequence alignment (NMSA). We define three new criteria for computing normalized scores when aligning multiple sequences, showing the NP-hardness and exact algorithms for solving the NMSA using those criteria. In addition, we provide approximation algorithms for MSA and NMSA for some classes of scoring matrices.

Cite as

Eloi Araujo, Luiz C. Rozante, Diego P. Rubert, and Fábio V. Martinez. Algorithms for Normalized Multiple Sequence Alignments. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.ISAAC.2021.40,
  author =	{Araujo, Eloi and Rozante, Luiz C. and Rubert, Diego P. and Martinez, F\'{a}bio V.},
  title =	{{Algorithms for Normalized Multiple Sequence Alignments}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.40},
  URN =		{urn:nbn:de:0030-drops-154734},
  doi =		{10.4230/LIPIcs.ISAAC.2021.40},
  annote =	{Keywords: Multiple sequence alignment, Normalized multiple sequence alignment, Algorithms and complexity}
}

Refine by Author
1 Araujo, Eloi
1 Martinez, Fábio V.
1 Rozante, Luiz C.
1 Rubert, Diego P.

Refine by Classification
1 Applied computing → Molecular sequence analysis
1 Theory of computation → Approximation algorithms analysis
1 Theory of computation → Problems, reductions and completeness

Refine by Keyword
1 Algorithms and complexity
1 Multiple sequence alignment
1 Normalized multiple sequence alignment

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Rozante, Luiz C."

Algorithms for Normalized Multiple Sequence Alignments

Abstract

Cite as

Thanks for your feedback!

Could not send message