title: Improvements on bicriteria pairwise sequence alignment: algorithms and applications.
abstract: BACKGROUND
  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.
  
  
  METHODS
  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.
authors: CISUC, Department of Informatics Engineering, University of Coimbra, Pólo II, Coimbra, Portugal.
authors: Maryam
authors: M
authors: Abbasi
authors: Luís
authors: L
authors: Paquete
authors: Arnaud
authors: A
authors: Liefooghe
authors: Miguel
authors: M
authors: Pinheiro
authors: Pedro
authors: P
authors: Matias
mesh_terms: D000465:Algorithms; D000818:Animals; D005800:Genes, Fungal; D006801:Humans; D016013:Likelihood Functions; D010802:Phylogeny; D011323:Primates; D016415:Sequence Alignment / Q000379:methods*; D012984:Software