{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T07:18:44Z","timestamp":1778311124461,"version":"3.51.4"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability and implementation: Source code is freely available for download at URL http:\/\/eden.dei.uc.pt\/\u223cpaquete\/MOSAL, implemented in C and supported on Linux, MAC OS and MS Windows.<\/jats:p>\n               <jats:p>Contact: \u00a0paquete@dei.uc.pt<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt098","type":"journal-article","created":{"date-parts":[[2013,2,24]],"date-time":"2013-02-24T01:19:45Z","timestamp":1361668785000},"page":"996-1003","source":"Crossref","is-referenced-by-count":9,"title":["Improvements on bicriteria pairwise sequence alignment: algorithms and applications"],"prefix":"10.1093","volume":"29","author":[{"given":"Maryam","family":"Abbasi","sequence":"first","affiliation":[{"name":"1 CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, 3030-290 Coimbra, Portugal, 2LIFL, UMR CNRS 8022, B\u00e2t. M3, Universit\u00e9 Lille 1, 59655 Villeneuve d\u2019Ascq, France and 3Bioinformatics Unit, Biocant, 3060-197 Cantanhede, Portugal"}]},{"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[{"name":"1 CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, 3030-290 Coimbra, Portugal, 2LIFL, UMR CNRS 8022, B\u00e2t. M3, Universit\u00e9 Lille 1, 59655 Villeneuve d\u2019Ascq, France and 3Bioinformatics Unit, Biocant, 3060-197 Cantanhede, Portugal"}]},{"given":"Arnaud","family":"Liefooghe","sequence":"additional","affiliation":[{"name":"1 CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, 3030-290 Coimbra, Portugal, 2LIFL, UMR CNRS 8022, B\u00e2t. M3, Universit\u00e9 Lille 1, 59655 Villeneuve d\u2019Ascq, France and 3Bioinformatics Unit, Biocant, 3060-197 Cantanhede, Portugal"}]},{"given":"Miguel","family":"Pinheiro","sequence":"additional","affiliation":[{"name":"1 CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, 3030-290 Coimbra, Portugal, 2LIFL, UMR CNRS 8022, B\u00e2t. M3, Universit\u00e9 Lille 1, 59655 Villeneuve d\u2019Ascq, France and 3Bioinformatics Unit, Biocant, 3060-197 Cantanhede, Portugal"}]},{"given":"Pedro","family":"Matias","sequence":"additional","affiliation":[{"name":"1 CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, 3030-290 Coimbra, Portugal, 2LIFL, UMR CNRS 8022, B\u00e2t. M3, Universit\u00e9 Lille 1, 59655 Villeneuve d\u2019Ascq, France and 3Bioinformatics Unit, Biocant, 3060-197 Cantanhede, Portugal"}]}],"member":"286","published-online":{"date-parts":[[2013,2,23]]},"reference":[{"key":"2023012810290338100_btt098-B1","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/978-3-642-15328-0_39","article-title":"The knapsack problem","volume-title":"Algorithms Unplugged","author":"Beier","year":"2011"},{"key":"2023012810290338100_btt098-B2","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1038\/nature08064","article-title":"Evolution of pathogenicity and sexual reproduction in eight candida genomes","volume":"459","author":"Butler","year":"2009","journal-title":"Nature"},{"key":"2023012810290338100_btt098-B3","first-page":"345","article-title":"A model of evolutionary change in proteins","volume-title":"Atlas of Protein Sequence and Structure","author":"Dayhoff","year":"1978"},{"key":"2023012810290338100_btt098-B4","volume-title":"Multicriteria Optimization","author":"Ehrgott","year":"2005"},{"key":"2023012810290338100_btt098-B5","doi-asserted-by":"crossref","first-page":"783","DOI":"10.2307\/2408678","article-title":"Confidence limits on phylogenies: an approach using the bootstrap","volume":"39","author":"Felsenstein","year":"1985","journal-title":"Evolution"},{"key":"2023012810290338100_btt098-B6","first-page":"432","article-title":"Parametric optimization of sequence alignment","volume-title":"Proceedings of the Third Annual ACM-Siam Symposium on Discrete Algorithms","author":"Gusfield","year":"1992"},{"key":"2023012810290338100_btt098-B7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023012810290338100_btt098-B8","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1109\/TCBB.2007.070203","article-title":"Multiobjective optimization in bioinformatics and computational biology","volume":"4","author":"Handl","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012810290338100_btt098-B9","doi-asserted-by":"crossref","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","volume-title":"Evolution of Protein Molecules","author":"Jukes","year":"1969"},{"key":"2023012810290338100_btt098-B10","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023012810290338100_btt098-B11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-02298-2_7","article-title":"Experiments with bicriteria sequence alignment","volume-title":"Cutting-Edge Research Topics on Multiple Criteria Decision Making","author":"Paquete","year":"2009"},{"key":"2023012810290338100_btt098-B12","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/008\/08","article-title":"Fast algorithm for optimal aligning of symbol sequences","volume-title":"Mathematical Methods of the Analysis of Biopolymer Sequences","author":"Roytberg","year":"1992"},{"key":"2023012810290338100_btt098-B13","first-page":"565","article-title":"Pareto-optimal alignment of biological sequences","volume":"44","author":"Roytberg","year":"1999","journal-title":"Biophysics"},{"key":"2023012810290338100_btt098-B14","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"2007","journal-title":"Mol. Biol. Evol."},{"key":"2023012810290338100_btt098-B15","volume-title":"Biological Systematics: Principles and Applications","author":"Schuh","year":"2009"},{"key":"2023012810290338100_btt098-B16","volume-title":"Multiple Criteria Optimization: Theory, Computation, and Application","author":"Steuer","year":"1986"},{"key":"2023012810290338100_btt098-B17","doi-asserted-by":"crossref","first-page":"2731","DOI":"10.1093\/molbev\/msr121","article-title":"Mega5: molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods","volume":"28","author":"Tamura","year":"2011","journal-title":"Mol. Biol. Evol."},{"key":"2023012810290338100_btt098-B18","doi-asserted-by":"crossref","first-page":"2383","DOI":"10.1093\/bioinformatics\/btq439","article-title":"Multi-objective pairwise RNA sequence alignment","volume":"26","author":"Taneda","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012810290338100_btt098-B19","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"Balibase 3.0: latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/8\/996\/48897089\/bioinformatics_29_8_996.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/8\/996\/48897089\/bioinformatics_29_8_996.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:08:47Z","timestamp":1674907727000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/8\/996\/230990"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,23]]},"references-count":19,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2013,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt098","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,4,15]]},"published":{"date-parts":[[2013,2,23]]}}}