{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T11:02:12Z","timestamp":1774263732544,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Continuous-time Markov models allow flexible, parametrically succinct descriptions of sequence divergence. Non-reversible forms of these models are more biologically realistic but are challenging to develop. The instantaneous rate matrices defined for these models are typically transformed into substitution probability matrices using a matrix exponentiation algorithm that employs eigendecomposition, but this algorithm has characteristic vulnerabilities that lead to significant errors when a rate matrix possesses certain 'pathological' properties. Here we tested whether pathological rate matrices exist in nature, and consider the suitability of different algorithms to their computation.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We used concatenated protein coding gene alignments from microbial genomes, primate genomes and independent intron alignments from primate genomes. The Taylor series expansion and eigendecomposition matrix exponentiation algorithms were compared to the less widely employed, but more robust, Pad\u00e9 with scaling and squaring algorithm for nucleotide, dinucleotide, codon and trinucleotide rate matrices. Pathological dinucleotide and trinucleotide matrices were evident in the microbial data set, affecting the eigendecomposition and Taylor algorithms respectively. Even using a conservative estimate of matrix error (occurrence of an invalid probability), both Taylor and eigendecomposition algorithms exhibited substantial error rates: ~100% of all exonic trinucleotide matrices were pathological to the Taylor algorithm while ~10% of codon positions 1 and 2 dinucleotide matrices and intronic trinucleotide matrices, and ~30% of codon matrices were pathological to eigendecomposition. The majority of Taylor algorithm errors derived from occurrence of multiple unobserved states. A small number of negative probabilities were detected from the Pad\u00e9 algorithm on trinucleotide matrices that were attributable to machine precision. Although the Pad\u00e9 algorithm does not facilitate caching of intermediate results, it was up to 3\u00d7 faster than eigendecomposition on the same matrices.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>Development of robust software for computing non-reversible dinucleotide, codon and higher evolutionary models requires implementation of the Pad\u00e9 with scaling and squaring algorithm.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-550","type":"journal-article","created":{"date-parts":[[2008,12,20]],"date-time":"2008-12-20T07:13:23Z","timestamp":1229757203000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Pathological rate matrices: from primates to pathogens"],"prefix":"10.1186","volume":"9","author":[{"given":"Harold W","family":"Schranz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Von Bing","family":"Yap","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Easteal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Knight","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gavin A","family":"Huttley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,12,19]]},"reference":[{"issue":"12","key":"2535_CR1","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1101\/gr.8.12.1233","volume":"8","author":"P Lio","year":"1998","unstructured":"Lio P, Goldman N: Models of molecular evolution and phylogeny. Genome Res 1998, 8(12):1233\u201344.","journal-title":"Genome Res"},{"issue":"10","key":"2535_CR2","doi-asserted-by":"publisher","first-page":"2034","DOI":"10.1002\/1097-0142(19840515)53:10<2034::AID-CNCR2820531005>3.0.CO;2-S","volume":"53","author":"B Ames","year":"1984","unstructured":"Ames B: The detection of environmental mutagens and potential carcinogens. Cancer 1984, 53(10):2034\u201340. Publisher Full Text 10.1002\/1097-0142(19840515)53:10<2034::AID-CNCR2820531005>3.0.CO;2-S","journal-title":"Cancer"},{"issue":"4","key":"2535_CR3","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/PL00006158","volume":"44","author":"JG Lawrence","year":"1997","unstructured":"Lawrence JG, Ochman H: Amelioration of Bacterial Genomes: Rates of Change and Exchange. Journal of Molecular Evolution 1997, 44(4):383\u2013397. 10.1007\/PL00006158","journal-title":"Journal of Molecular Evolution"},{"issue":"3","key":"2535_CR4","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/10635150490445779","volume":"53","author":"PG Foster","year":"2004","unstructured":"Foster PG: Modeling compositional heterogeneity. Syst Biol 2004, 53(3):485\u201395. 10.1080\/10635150490445779","journal-title":"Syst Biol"},{"issue":"9","key":"2535_CR5","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1093\/oxfordjournals.molbev.a004216","volume":"19","author":"E Schadt","year":"2002","unstructured":"Schadt E, Lange K: Codon and rate variation models in molecular phylogeny. Mol Biol Evol 2002, 19(9):1534\u20131549.","journal-title":"Mol Biol Evol"},{"key":"2535_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/S00361445024180","volume":"45","author":"CB Moler","year":"2003","unstructured":"Moler CB, Van Loan CF: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review 2003, 45: 3\u201349. 10.1137\/S00361445024180","journal-title":"SIAM Review"},{"key":"2535_CR7","volume-title":"Matrix computations","author":"GH Golub","year":"1996","unstructured":"Golub GH, Loan CFV: Matrix computations. 3rd edition. Baltimore, MD, USA: Johns Hopkins University Press; 1996.","edition":"3"},{"issue":"4","key":"2535_CR8","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1137\/0714039","volume":"14","author":"RC Ward","year":"1977","unstructured":"Ward RC: Numerical Computation of the Matrix Exponential with Accuracy Estimate. SIAM Journal on Numerical Analysis 1977, 14(4):600\u2013610. 10.1137\/0714039","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"3","key":"2535_CR9","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF02162166","volume":"10","author":"R Smith","year":"1967","unstructured":"Smith R: The condition numbers of the matrix eigenvalue problem. Numerische Mathematik 1967, 10(3):232\u2013240. 10.1007\/BF02162166","journal-title":"Numerische Mathematik"},{"issue":"3","key":"2535_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01400115","volume":"51","author":"J Demmel","year":"1987","unstructured":"Demmel J: On condition numbers and the distance to the nearest ill-posed problem. Numerische Mathematik 1987, 51(3):251\u2013289. 10.1007\/BF01400115","journal-title":"Numerische Mathematik"},{"issue":"2","key":"2535_CR11","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/152613.152617","volume":"19","author":"Z Bai","year":"1993","unstructured":"Bai Z, Demmel J, McKenney A: On computing condition numbers for the nonsymmetric eigenproblem. ACM Trans Math Softw 1993, 19(2):202\u2013223. 10.1145\/152613.152617","journal-title":"ACM Trans Math Softw"},{"issue":"5822","key":"2535_CR12","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1126\/science.1139247","volume":"316","author":"RA Gibbs","year":"2007","unstructured":"Gibbs RA, Rogers J, Katze MG, Bumgarner R, Weinstock GM, Mardis ER, Remington KA, Strausberg RL, Venter JC, Wilson RK, Batzer MA, Bustamante CD, Eichler EE, Hahn MW, Hardison RC, Makova KD, Miller W, Milosavljevic A, Palermo RE, Siepel A, Sikela JM, Attaway T, Bell S, Bernard KE, Buhay CJ, Chandrabose MN, Dao M, Davis C, Delehaunty KD, Ding Y, Dinh HH, Dugan-Rocha S, Fulton LA, Gabisi RA, Garner TT, Godfrey J, Hawes AC, Hernandez J, Hines S, Holder M, Hume J, Jhangiani SN, Joshi V, Khan ZM, Kirkness EF, Cree A, Fowler RG, Lee S, Lewis LR, Li Z, Liu YS, Moore SM, Muzny D, Nazareth LV, Ngo DN, Okwuonu GO, Pai G, Parker D, Paul HA, Pfannkoch C, Pohl CS, Rogers YH, Ruiz SJ, Sabo A, Santibanez J, Schneider BW, Smith SM, Sodergren E, Svatek AF, Utterback TR, Vattathil S, Warren W, White CS, Chinwalla AT, Feng Y, Halpern AL, Hillier LW, Huang X, Minx P, Nelson JO, Pepin KH, Qin X, Sutton GG, Venter E, Walenz BP, Wallis JW, Worley KC, Yang SP, Jones SM, Marra MA, Rocchi M, Schein JE, Baertsch R, Clarke L, Csuros M, Glasscock J, Harris RA, Havlak P, Jackson AR, Jiang H, Liu Y, Messina DN, Shen Y, Song HXZ, Wylie T, Zhang L, Birney E, Han K, Konkel MK, Lee J, Smit AFA, Ullmer B, Wang H, Xing J, Burhans R, Cheng Z, Karro JE, Ma J, Raney B, She X, Cox MJ, Demuth JP, Dumas LJ, Han SG, Hopkins J, Karimpour-Fard A, Kim YH, Pollack JR, Vinar T, Addo-Quaye C, Degenhardt J, Denby A, Hubisz MJ, Indap A, Kosiol C, Lahn BT, Lawson HA, Marklein A, Nielsen R, Vallender EJ, Clark AG, Ferguson B, Hernandez RD, Hirani K, Kehrer-Sawatzki H, Kolb J, Patil S, Pu LL, Ren Y, Smith DG, Wheeler DA, Schenck I, Ball EV, Chen R, Cooper DN, Giardine B, Hsu F, Kent WJ, Lesk A, Nelson DL, O'brien WE, Prufer K, Stenson PD, Wallace JC, Ke H, Liu XM, Wang P, Xiang AP, Yang F, Barber GP, Haussler D, Karolchik D, Kern AD, Kuhn RM, Smith KE, Zwieg AS: Evolutionary and biomedical insights from the rhesus macaque genome. Science 2007, 316(5822):222\u2013234. 10.1126\/science.1139247","journal-title":"Science"},{"issue":"4","key":"2535_CR13","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1137\/1018113","volume":"18","author":"GH Golub","year":"1976","unstructured":"Golub GH, Wilkinson JH: Ill-Conditioned Eigensystems and the Computation of the Jordan Canonical Form. SIAM Review 1976, 18(4):578\u2013619. 10.1137\/1018113","journal-title":"SIAM Review"},{"key":"2535_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02165660","volume":"15","author":"A Ruhe","year":"1970","unstructured":"Ruhe A: Properties of a matrix with a very ill-conditioned eigenproblem. Numerische Mathematik 1970, 15: 57\u201360. 10.1007\/BF02165660","journal-title":"Numerische Mathematik"},{"key":"2535_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/j.laa.2004.09.008","volume":"395","author":"R Alam","year":"2005","unstructured":"Alam R: On the construction of nearest defective matrices to a normal matrix. Linear Algebra and Its Applications 2005, 395: 367\u2013370. 10.1016\/j.laa.2004.09.008","journal-title":"Linear Algebra and Its Applications"},{"key":"2535_CR16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719673","volume-title":"Lectures on Finite Precision Computations","author":"F Chaitin-Chatelin","year":"1996","unstructured":"Chaitin-Chatelin F, Frayss\u00e9 V: Lectures on Finite Precision Computations. Philadelphia: SIAM; 1996."},{"issue":"5","key":"2535_CR17","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1093\/oxfordjournals.molbev.a025957","volume":"15","author":"Z Yang","year":"1998","unstructured":"Yang Z: Likelihood ratio tests for detecting positive selection and application to primate lysozyme evolution. Mol Biol Evol 1998, 15(5):568\u201373.","journal-title":"Mol Biol Evol"},{"issue":"8","key":"2535_CR18","doi-asserted-by":"publisher","first-page":"R171","DOI":"10.1186\/gb-2007-8-8-r171","volume":"8","author":"R Knight","year":"2007","unstructured":"Knight R, Maxwell P, Birmingham A, Carnes J, Caporaso J, Easton B, Eaton M, Hamady M, Lindsay H, Liu Z, Lozupone C, McDonald D, Robeson M, Sammut R, Smit S, Wakefield M, Widmann J, Wikman S, Wilson S, Ying H, Huttley G: PyCogent: a toolkit for making sense from sequence. Genome Biol 2007, 8(8):R171. 10.1186\/gb-2007-8-8-r171","journal-title":"Genome Biol"},{"key":"2535_CR19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512","volume-title":"Matrix Analysis and Applied Linear Algebra","author":"C Meyer","year":"2000","unstructured":"Meyer C: Matrix Analysis and Applied Linear Algebra. Society for Industrial Mathematics; 2000."},{"key":"2535_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-5-1","volume":"5","author":"A Butterfield","year":"2004","unstructured":"Butterfield A, Vedagiri V, Lang E, Lawrence C, Wakefield MJ, Isaev A, Huttley GA: PyEvolve: a toolkit for statistical modelling of molecular evolution. BMC Bioinformatics 2004, 5: 1. 10.1186\/1471-2105-5-1","journal-title":"BMC Bioinformatics"},{"key":"2535_CR21","unstructured":"Numeric python[http:\/\/numpy.scipy.org]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-550.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:46:15Z","timestamp":1630467975000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2535"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-550","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]},"assertion":[{"value":"30 June 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"550"}}