{"entities":{"Q1091978":{"pageid":1102730,"ns":120,"title":"Item:Q1091978","lastrevid":49082581,"modified":"2026-01-06T13:56:05Z","type":"item","id":"Q1091978","labels":{"en":{"language":"en","value":"Computational complexity of inferring phylogenies from dissimilarity matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4012389"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$33C79CF2-FA91-433E-BC0E-2288EE1C4881","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf5f2f68de3dec74855811aef9e1bd9de52889b2","datavalue":{"value":{"text":"Computational complexity of inferring phylogenies from dissimilarity matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091978$32CFEA5D-D11F-438D-9439-CBB07AE5989A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f922f17f5c855c44ec1afee99ae14407d7ffd08b","datavalue":{"value":"0623.92018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$A76CD128-52FA-4BFF-B208-0D8557043A5C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e9e0ff76bb56245f3079320eb221c3b885a0205d","datavalue":{"value":"10.1007/BF02458863","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$AB2A12FF-2236-420A-AFF9-A7B489BCC1D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c08128d79885121c69f38cbde673311f6a96775","datavalue":{"value":{"entity-type":"item","numeric-id":585630,"id":"Q585630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$5E200037-4FDF-4A08-A685-DECF314AE94E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4a6f7d015df5f02e6fe02ce89bcd002530eaade1","datavalue":{"value":{"entity-type":"item","numeric-id":85622,"id":"Q85622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$1B804F46-D937-45D3-A4A7-7347862FC101","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1091978$19E7B99F-795B-4F97-BFA2-D3422693BE7E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6cde5fd4719b97a15d3cbe959257904e93535b6d","datavalue":{"value":"Molecular biologists strive to infer evolutionary relationships from quantitative macromolecular comparisons obtained by immunological, DNA hybridization, electrophoretic or amino acid sequencing techniques. The problem is to find unrooted phylogenies that best approximate a given dissimilarity matrix according to a goodness-of-fit measure, for example the least-squares-fit criterion or Farris's f statistic [Am. Nat. 106, 645-668 (1972)]. Computational costs of known algorithms guaranteeing optimal solutions to these problems increase exponentially with problem size; practical computational considerations limit the algorithms to analyzing small problems.    It is established here that problems of phylogenetic inference based on the least-squares-fit criterion and the f statistic are NP-complete and thus are so difficult computationally that efficient optimal algorithms are unlikely to exist for them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$C7B658D0-4D5C-4C2F-9EEC-B65566C3B16B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"408a79c1bfecc6ff58b5150b55e32f4d3c10746b","datavalue":{"value":"92Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$DF782EA4-090F-4E53-9C1F-E50C2B34ED02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$6719DFAD-F2AB-4CD2-B2B6-A24DF497580A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97a8bf1fc3512f3d46d0035faed31c3e7787a615","datavalue":{"value":"4012389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$BF8B894F-E629-4573-A0C7-6D99BA5A9AA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4178eeb959aa707238abf34355427d0031bbd3d","datavalue":{"value":"biochemistry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$E6171D4E-2DE0-4550-84A0-ECC4748858B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a44cba0b491d16b7e340284840f84e15910df75c","datavalue":{"value":"amino acid sequencing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$2A33B7A8-CDE5-4CDA-8AC1-E91A2ECB0C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"315b12e22c978d5fed8c252041a9c9f4729d5e11","datavalue":{"value":"unrooted phylogenies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$E2D140E0-4BC5-4DF2-83F0-BCDFF1D167E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a2f99bd376a80c03d5f07b4eec27d456648ed4a","datavalue":{"value":"dissimilarity matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$F76B2A10-543A-4EA9-AC9B-50A1BCEEC0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cada029336c6cfb2c243a2b3bce1bed7882b2c94","datavalue":{"value":"least-squares-fit criterion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$1F8938B4-698C-4D07-9D76-D3508F0B1CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1badef508ca24e6a954c73a1cfdac4df85569e0","datavalue":{"value":"Farris's f statistic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$7B27220F-F70E-475F-999A-F9417499FCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"212b93bcee7ac92be6b2a3420008f6d1b5975f7d","datavalue":{"value":"phylogenetic inference","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$783C0858-61AF-439B-BDD2-7E5B3DD39739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091978$F0264BA5-BA46-4F19-8500-B813CE8F67BE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f79dc18ceaddbe1665e908cc8e52a43652a0889a","datavalue":{"value":"Q69418195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$284E3AB0-5A2C-4A3D-9DED-38857398C701","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$1C86DE78-5001-4B0D-832D-C33BA3BFEFB8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d870108988893b45925715dedf4ad0faaaafe2","datavalue":{"value":{"entity-type":"item","numeric-id":103560,"id":"Q103560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$025010B7-C1B2-4239-A9B7-5138F2D25EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25781826b9d7266dcc5628f18e722a47d9ceb748","datavalue":{"value":{"entity-type":"item","numeric-id":1086183,"id":"Q1086183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$C2523F2D-B6E1-44D2-8E92-6746F8F48958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e871b75dfa883ed59e8f6ae3fa423f4e8e39f0e","datavalue":{"value":{"entity-type":"item","numeric-id":4404099,"id":"Q4404099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$2AE7143E-389C-4D1B-9933-C476F375AFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"200584f07d75117dc0c9834797f6e5d1cba1435b","datavalue":{"value":{"entity-type":"item","numeric-id":1167073,"id":"Q1167073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$EEA39956-3643-4C92-BC40-5E1B03A674E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$B0424D3C-E7EB-42A7-A80A-938364707966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b297339092ca9cc405cd7a74b9973569e5287b43","datavalue":{"value":{"entity-type":"item","numeric-id":1167074,"id":"Q1167074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$A50B97E4-1AB7-49DF-AD41-C03952F09BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29b172e4ad045f3155d3b563ba0cf247064f0a90","datavalue":{"value":{"entity-type":"item","numeric-id":5329581,"id":"Q5329581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$8DDF2CB2-0D76-4E83-A6C8-D1D5EF8B15A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcf6016aa6a6bb4076c71393c202be8c4bc90220","datavalue":{"value":{"entity-type":"item","numeric-id":4085109,"id":"Q4085109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$3418D0F7-DC54-4E22-89BD-9280DC5FB3DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"150a71b1a29ca7a7a60745ed043ee92190331a73","datavalue":{"value":{"entity-type":"item","numeric-id":1102746,"id":"Q1102746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091978$90E7ECEA-C749-43CC-B9C1-4EA514ABE219","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2c55c160450ca21b0a4675cbe9162e9fa47a11be","datavalue":{"value":"https://doi.org/10.1007/bf02458863","type":"string"},"datatype":"url"},"type":"statement","id":"Q1091978$1F9672CA-108A-4A91-A246-BDBA1BBB8E31","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba1275a8920fb44c9ee3786df12d775d209d24ed","datavalue":{"value":"W4237132695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091978$8B52521C-6837-4644-8D96-DF56265BBE2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"842678423a24a21baa5d191f6538da5722a31f5c","datavalue":{"value":{"entity-type":"item","numeric-id":1086183,"id":"Q1086183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a1f32f022fc4b22930bc597688782cdbb7ee5c3","datavalue":{"value":{"amount":"+0.8419914245605469","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1091978$7137DB4F-AC23-459F-A474-A1A6A507B8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a4557394e38443f3b0a2734efaa3862e07e4975","datavalue":{"value":{"entity-type":"item","numeric-id":4305354,"id":"Q4305354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa786fabfc349c755f9984aa0e395938168233d0","datavalue":{"value":{"amount":"+0.8330870866775513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1091978$1E833493-0401-4E08-93E9-8EE1FA747BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f385ac2106f88e0ea4048b124e18e8d4f54a307","datavalue":{"value":{"entity-type":"item","numeric-id":1306398,"id":"Q1306398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2c07f0c9f0aa223e014c3ccb2d955f7d0fe7722","datavalue":{"value":{"amount":"+0.8277461528778076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1091978$8E147547-4573-44A8-8ACA-9A85CF9ECACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a77e6272cfc4c5cdf2842ad6d99ec9ab511958ff","datavalue":{"value":{"entity-type":"item","numeric-id":4364583,"id":"Q4364583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84856c9337fda0dfc87caa9d3d8328e94e37334f","datavalue":{"value":{"amount":"+0.8265154957771301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1091978$2C69BB0D-04C9-41F3-BFFC-536781AE4468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbf7101b35e974e58af59ccb97a60312b46ac60d","datavalue":{"value":{"entity-type":"item","numeric-id":2465625,"id":"Q2465625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84856c9337fda0dfc87caa9d3d8328e94e37334f","datavalue":{"value":{"amount":"+0.8265154957771301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1091978$AA1F569F-C346-4E2F-BA75-FBB192D8DFBD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1091978","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1091978"}}}}}