Title :

Improvements on bicriteria pairwise sequence alignment: algorithms and applications

Author(s) :

Abbasi, Maryam [Auteur]
Evolutionary and Complex Systems Group [ECOS Group]
Paquete, Luis [Auteur correspondant]
Evolutionary and Complex Systems Group [ECOS Group]
Liefooghe, Arnaud [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Pinheiro, Miguel [Auteur]
Matias, Pedro [Auteur]
Evolutionary and Complex Systems Group [ECOS Group]

Journal title :

Bioinformatics

Pages :

996-1003

Publisher :

Oxford University Press (OUP)

Publication date :

2013

ISSN :

1367-4803

HAL domain(s) :

Informatique [cs]/Bio-informatique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
Informatique [cs]/Recherche opérationnelle [cs.RO]

English abstract : [en]

Motivation: In this article, we consider the bicriteria pairwise sequence alignment problem and propose extensions of dynamic programming algorithms for several problem variants with a novel pruning technique that efficiently ...
Show more >Motivation: In this article, we consider the bicriteria pairwise sequence alignment problem and propose extensions of dynamic programming algorithms for several problem variants with a novel pruning technique that efficiently reduces the number of states to be processed. Moreover, we present a method for the construction of phylogenetic trees based on this bicriteria framework. Two exemplary cases are discussed. Results: Numerical results on a real dataset show that this approach is very fast in practice. The pruning technique saves up to 90% in memory usage and 80% in CPU time. Based on this method, phylogenetic trees are constructed from real-life data. In addition of providing complementary information, some of these trees match those obtained by the Maximum Likelihood method. Availability and implementation: Source code is freely available for download at URL http://eden.dei.uc.pt/paquete/MOSAL/, implemented in C and supported on Linux, MAC OS and MS Windows.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL