Best match graphs. View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-04-09

AUTHORS

Manuela Geiß, Edgar Chávez, Marcos González Laffitte, Alitzel López Sánchez, Bärbel M R Stadler, Dulce I Valdivia, Marc Hellmuth, Maribel Hernández Rosales, Peter F Stadler

ABSTRACT

Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and [Formula: see text] an assignment of leaves of T to species. The best match graph [Formula: see text] is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species [Formula: see text]. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether [Formula: see text] derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains [Formula: see text], which can also be constructed in cubic time. More... »

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00285-019-01332-9

DOI

http://dx.doi.org/10.1007/s00285-019-01332-9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1113327961

PUBMED

https://www.ncbi.nlm.nih.gov/pubmed/30968198


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0604", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Genetics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Leipzig University", 
          "id": "https://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "Bioinformatics Group, Department of Computer Science, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany.", 
            "Interdisciplinary Center of Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gei\u00df", 
        "givenName": "Manuela", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "CONACYT-Instituto de Matem\u00e1ticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Quer\u00e9taro, QRO, Mexico."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ch\u00e1vez", 
        "givenName": "Edgar", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "CONACYT-Instituto de Matem\u00e1ticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Quer\u00e9taro, QRO, Mexico."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gonz\u00e1lez Laffitte", 
        "givenName": "Marcos", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "CONACYT-Instituto de Matem\u00e1ticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Quer\u00e9taro, QRO, Mexico."
          ], 
          "type": "Organization"
        }, 
        "familyName": "L\u00f3pez S\u00e1nchez", 
        "givenName": "Alitzel", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Mathematics in the Sciences", 
          "id": "https://www.grid.ac/institutes/grid.419532.8", 
          "name": [
            "Max-Planck-Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, 04103, Leipzig, Germany."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stadler", 
        "givenName": "B\u00e4rbel M R", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Autonomous University of Aguascalientes", 
          "id": "https://www.grid.ac/institutes/grid.412851.b", 
          "name": [
            "Centro de Ciencias B\u00e1sicas, Universidad Aut\u00f3noma de Aguascalientes, Av. Universidad 940, 20131, Aguascalientes, AGS, Mexico.", 
            "Instituto de Matem\u00e1ticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Quer\u00e9taro, QRO, Mexico."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Valdivia", 
        "givenName": "Dulce I", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Saarland University", 
          "id": "https://www.grid.ac/institutes/grid.11749.3a", 
          "name": [
            "Institute of Mathematics and Computer Science, University of Greifswald, Walther-Rathenau-Stra\u00dfe 47, 17487, Greifswald, Germany.", 
            "Center for Bioinformatics, Saarland University, Building E 2.1, P.O. Box 151150, 66041, Saarbr\u00fccken, Germany."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hellmuth", 
        "givenName": "Marc", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "CONACYT-Instituto de Matem\u00e1ticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Quer\u00e9taro, QRO, Mexico."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hern\u00e1ndez Rosales", 
        "givenName": "Maribel", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Santa Fe Institute", 
          "id": "https://www.grid.ac/institutes/grid.209665.e", 
          "name": [
            "Bioinformatics Group, Department of Computer Science, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "Interdisciplinary Center of Bioinformatics, University of Leipzig, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "Max-Planck-Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, 04103, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Leipzig University, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "Competence Center for Scalable Data Services and Solutions, Leipzig University, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "Leipzig Research Center for Civilization Diseases, Leipzig University, H\u00e4rtelstra\u00dfe 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.", 
            "Institute of Theoretical Chemistry, University of Vienna, W\u00e4hringerstra\u00dfe 17, 1090, Vienna, Austria. studla@bioinf.uni-leipzig.de.", 
            "Facultad de Ciencias, Universidad National de Colombia, Sede Bogot\u00e1, Colombia. studla@bioinf.uni-leipzig.de.", 
            "Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM, 87501, USA. studla@bioinf.uni-leipzig.de."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stadler", 
        "givenName": "Peter F", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0167-6423(89)90039-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001431838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jmbi.1998.2144", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002190651"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/gkr308", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002392993"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1371/journal.pcbi.1000262", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005269052"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.mbs.2006.11.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005909688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/aama.1995.1020", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008822253"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00285-012-0525-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009586472", 
          "https://doi.org/10.1007/s00285-012-0525-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nmeth.3830", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009914770", 
          "https://doi.org/10.1038/nmeth.3830"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1371/journal.pone.0105015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011835816"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(73)90109-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012351613"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2006.03.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015244524"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2014.10.045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015472719"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-12-124", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021782995", 
          "https://doi.org/10.1186/1471-2105-12-124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-12-124", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021782995", 
          "https://doi.org/10.1186/1471-2105-12-124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2164-15-s6-s12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022056400", 
          "https://doi.org/10.1186/1471-2164-15-s6-s12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.96.6.2896", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023469671"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/s13015-016-0067-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024877337", 
          "https://doi.org/10.1186/s13015-016-0067-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.1412770112", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025894422"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00285-016-1084-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034663401", 
          "https://doi.org/10.1007/s00285-016-1084-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00285-016-1084-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034663401", 
          "https://doi.org/10.1007/s00285-016-1084-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035576733", 
          "https://doi.org/10.1007/pl00009268"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(95)00165-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037202960"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/gbe/evs100", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039510355"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.278.5338.631", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039646901"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/oxfordjournals.molbev.a003907", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040067893"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg1659", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041578587", 
          "https://doi.org/10.1038/nrg1659"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nrg1659", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041578587", 
          "https://doi.org/10.1038/nrg1659"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(02)00250-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046361339"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btg213", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046587046"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btm585", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050090819"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/gbe/evt132", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051400194"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0201008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841171"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0210030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841583"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0213024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841758"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0217079", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842098"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10878-017-0111-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1074215713", 
          "https://doi.org/10.1007/s10878-017-0111-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10878-017-0111-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1074215713", 
          "https://doi.org/10.1007/s10878-017-0111-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1074273155", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-13-s19-s6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083681507", 
          "https://doi.org/10.1186/1471-2105-13-s19-s6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-13-s19-s6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083681507", 
          "https://doi.org/10.1186/1471-2105-13-s19-s6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/s13015-017-0096-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084251763", 
          "https://doi.org/10.1186/s13015-017-0096-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/s13015-017-0096-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084251763", 
          "https://doi.org/10.1186/s13015-017-0096-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btx229", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085320664"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1558-5646.1989.tb04263.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085729742"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-017-0330-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085886267", 
          "https://doi.org/10.1007/s00453-017-0330-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-017-0330-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085886267", 
          "https://doi.org/10.1007/s00453-017-0330-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973006.4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088800965"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/s13015-017-0114-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091371079", 
          "https://doi.org/10.1186/s13015-017-0114-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/fm-70-1-59-101", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091799716"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.gpb.2017.07.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092636759"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4939-7463-4_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1100059111", 
          "https://doi.org/10.1007/978-1-4939-7463-4_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00285-018-1260-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105165655", 
          "https://doi.org/10.1007/s00285-018-1260-8"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04-09", 
    "datePublishedReg": "2019-04-09", 
    "description": "Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and [Formula: see text] an assignment of leaves of T to species. The best match graph [Formula: see text] is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species [Formula: see text]. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether [Formula: see text] derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains [Formula: see text], which can also be constructed in cubic time.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00285-019-01332-9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1081642", 
        "issn": [
          "0303-6812", 
          "1432-1416"
        ], 
        "name": "Journal of Mathematical Biology", 
        "type": "Periodical"
      }
    ], 
    "name": "Best match graphs.", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00285-019-01332-9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1113327961"
        ]
      }, 
      {
        "name": "nlm_unique_id", 
        "type": "PropertyValue", 
        "value": [
          "7502105"
        ]
      }, 
      {
        "name": "pubmed_id", 
        "type": "PropertyValue", 
        "value": [
          "30968198"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00285-019-01332-9", 
      "https://app.dimensions.ai/details/publication/pub.1113327961"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T09:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000375_0000000375/records_91469_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00285-019-01332-9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00285-019-01332-9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00285-019-01332-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00285-019-01332-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00285-019-01332-9'


 

This table displays all metadata directly associated to this object as RDF triples.

285 TRIPLES      20 PREDICATES      69 URIs      16 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00285-019-01332-9 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author N6c863d64aeae4e7ca30bfad874b4d79d
4 schema:citation sg:pub.10.1007/978-1-4939-7463-4_1
5 sg:pub.10.1007/pl00009268
6 sg:pub.10.1007/s00285-012-0525-x
7 sg:pub.10.1007/s00285-016-1084-3
8 sg:pub.10.1007/s00285-018-1260-8
9 sg:pub.10.1007/s00453-017-0330-4
10 sg:pub.10.1007/s10878-017-0111-7
11 sg:pub.10.1038/nmeth.3830
12 sg:pub.10.1038/nrg1659
13 sg:pub.10.1186/1471-2105-12-124
14 sg:pub.10.1186/1471-2105-13-s19-s6
15 sg:pub.10.1186/1471-2164-15-s6-s12
16 sg:pub.10.1186/s13015-016-0067-7
17 sg:pub.10.1186/s13015-017-0096-x
18 sg:pub.10.1186/s13015-017-0114-z
19 https://app.dimensions.ai/details/publication/pub.1074273155
20 https://doi.org/10.1006/aama.1995.1020
21 https://doi.org/10.1006/jmbi.1998.2144
22 https://doi.org/10.1016/0012-365x(73)90109-x
23 https://doi.org/10.1016/0020-0190(95)00165-4
24 https://doi.org/10.1016/0167-6423(89)90039-7
25 https://doi.org/10.1016/j.dam.2006.03.005
26 https://doi.org/10.1016/j.gpb.2017.07.002
27 https://doi.org/10.1016/j.mbs.2006.11.005
28 https://doi.org/10.1016/j.tcs.2014.10.045
29 https://doi.org/10.1016/s0166-218x(02)00250-0
30 https://doi.org/10.1073/pnas.1412770112
31 https://doi.org/10.1073/pnas.96.6.2896
32 https://doi.org/10.1093/bioinformatics/btg213
33 https://doi.org/10.1093/bioinformatics/btm585
34 https://doi.org/10.1093/bioinformatics/btx229
35 https://doi.org/10.1093/gbe/evs100
36 https://doi.org/10.1093/gbe/evt132
37 https://doi.org/10.1093/nar/gkr308
38 https://doi.org/10.1093/oxfordjournals.molbev.a003907
39 https://doi.org/10.1111/j.1558-5646.1989.tb04263.x
40 https://doi.org/10.1126/science.278.5338.631
41 https://doi.org/10.1137/0201008
42 https://doi.org/10.1137/0210030
43 https://doi.org/10.1137/0213024
44 https://doi.org/10.1137/0217079
45 https://doi.org/10.1137/1.9781611973006.4
46 https://doi.org/10.1371/journal.pcbi.1000262
47 https://doi.org/10.1371/journal.pone.0105015
48 https://doi.org/10.4064/fm-70-1-59-101
49 schema:datePublished 2019-04-09
50 schema:datePublishedReg 2019-04-09
51 schema:description Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and [Formula: see text] an assignment of leaves of T to species. The best match graph [Formula: see text] is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species [Formula: see text]. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether [Formula: see text] derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains [Formula: see text], which can also be constructed in cubic time.
52 schema:genre research_article
53 schema:inLanguage en
54 schema:isAccessibleForFree false
55 schema:isPartOf sg:journal.1081642
56 schema:name Best match graphs.
57 schema:productId N1014224313634ad997ee4408326750ab
58 N33e78b42c7694f0baabbcd575135787e
59 Nb5c48aff8bc94e68a647427be9733728
60 Neec8241f0ead4293b14a542cf9510296
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1113327961
62 https://doi.org/10.1007/s00285-019-01332-9
63 schema:sdDatePublished 2019-04-15T09:04
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Nebd932fbea9f460c929341655799a59f
66 schema:url http://link.springer.com/10.1007/s00285-019-01332-9
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N1014224313634ad997ee4408326750ab schema:name pubmed_id
71 schema:value 30968198
72 rdf:type schema:PropertyValue
73 N14ed69062f4842ae83999522414f7bfe schema:name CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico.
74 rdf:type schema:Organization
75 N23970a197d6a48238e6c6acb0daa1e54 rdf:first N452cb5093ed2408d98f68469988af616
76 rdf:rest N48a1ce9d0abe496d901255e83e8859d2
77 N33e78b42c7694f0baabbcd575135787e schema:name dimensions_id
78 schema:value pub.1113327961
79 rdf:type schema:PropertyValue
80 N3b2100a7429e4af0a8f87acf496c89e1 schema:affiliation https://www.grid.ac/institutes/grid.209665.e
81 schema:familyName Stadler
82 schema:givenName Peter F
83 rdf:type schema:Person
84 N452cb5093ed2408d98f68469988af616 schema:affiliation Nc2f1c96fe59b454291166a6252569b27
85 schema:familyName López Sánchez
86 schema:givenName Alitzel
87 rdf:type schema:Person
88 N48a1ce9d0abe496d901255e83e8859d2 rdf:first N6141e8e62bd347138f049d97964985e1
89 rdf:rest Nbf75063b54da42c6b6068fa9eda2a172
90 N54a8908e4af94fb4997ceb0afb6fc7ca rdf:first N5d68cb71bcad4b35b157de4edcb5afb8
91 rdf:rest Nffdf99da738f42e2af96033ce7dfe41d
92 N5d68cb71bcad4b35b157de4edcb5afb8 schema:affiliation https://www.grid.ac/institutes/grid.11749.3a
93 schema:familyName Hellmuth
94 schema:givenName Marc
95 rdf:type schema:Person
96 N5ef5f235825d49669d51014510ff5fcb rdf:first N65b4768fe4f54507957f44bc667b71b6
97 rdf:rest Ne4874a468e2b4a09be5bf7b98df96b56
98 N6141e8e62bd347138f049d97964985e1 schema:affiliation https://www.grid.ac/institutes/grid.419532.8
99 schema:familyName Stadler
100 schema:givenName Bärbel M R
101 rdf:type schema:Person
102 N65b4768fe4f54507957f44bc667b71b6 schema:affiliation N14ed69062f4842ae83999522414f7bfe
103 schema:familyName Chávez
104 schema:givenName Edgar
105 rdf:type schema:Person
106 N6c863d64aeae4e7ca30bfad874b4d79d rdf:first Nc315c3cc0b0c4071a827ba8ecf992f35
107 rdf:rest N5ef5f235825d49669d51014510ff5fcb
108 N7da4b126a40b4845b1c5b0e92d3a78ff schema:affiliation https://www.grid.ac/institutes/grid.412851.b
109 schema:familyName Valdivia
110 schema:givenName Dulce I
111 rdf:type schema:Person
112 N8e2ba63ff0684ba694afeecbc70e4673 schema:affiliation N9cccb19dcec640248bf211417c2106cb
113 schema:familyName González Laffitte
114 schema:givenName Marcos
115 rdf:type schema:Person
116 N9cccb19dcec640248bf211417c2106cb schema:name CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico.
117 rdf:type schema:Organization
118 Nb5c48aff8bc94e68a647427be9733728 schema:name doi
119 schema:value 10.1007/s00285-019-01332-9
120 rdf:type schema:PropertyValue
121 Nbf75063b54da42c6b6068fa9eda2a172 rdf:first N7da4b126a40b4845b1c5b0e92d3a78ff
122 rdf:rest N54a8908e4af94fb4997ceb0afb6fc7ca
123 Nc2f1c96fe59b454291166a6252569b27 schema:name CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico.
124 rdf:type schema:Organization
125 Nc315c3cc0b0c4071a827ba8ecf992f35 schema:affiliation https://www.grid.ac/institutes/grid.9647.c
126 schema:familyName Geiß
127 schema:givenName Manuela
128 rdf:type schema:Person
129 Nc4e93c39ac604907945afdaf3548ef82 schema:affiliation Nc7b31d658b7046deac3ec4a2c273492d
130 schema:familyName Hernández Rosales
131 schema:givenName Maribel
132 rdf:type schema:Person
133 Nc7b31d658b7046deac3ec4a2c273492d schema:name CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico.
134 rdf:type schema:Organization
135 Ncc781a4c3e1647a3997cb978fe9da40a rdf:first N3b2100a7429e4af0a8f87acf496c89e1
136 rdf:rest rdf:nil
137 Ne4874a468e2b4a09be5bf7b98df96b56 rdf:first N8e2ba63ff0684ba694afeecbc70e4673
138 rdf:rest N23970a197d6a48238e6c6acb0daa1e54
139 Nebd932fbea9f460c929341655799a59f schema:name Springer Nature - SN SciGraph project
140 rdf:type schema:Organization
141 Neec8241f0ead4293b14a542cf9510296 schema:name nlm_unique_id
142 schema:value 7502105
143 rdf:type schema:PropertyValue
144 Nffdf99da738f42e2af96033ce7dfe41d rdf:first Nc4e93c39ac604907945afdaf3548ef82
145 rdf:rest Ncc781a4c3e1647a3997cb978fe9da40a
146 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
147 schema:name Biological Sciences
148 rdf:type schema:DefinedTerm
149 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
150 schema:name Genetics
151 rdf:type schema:DefinedTerm
152 sg:journal.1081642 schema:issn 0303-6812
153 1432-1416
154 schema:name Journal of Mathematical Biology
155 rdf:type schema:Periodical
156 sg:pub.10.1007/978-1-4939-7463-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100059111
157 https://doi.org/10.1007/978-1-4939-7463-4_1
158 rdf:type schema:CreativeWork
159 sg:pub.10.1007/pl00009268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035576733
160 https://doi.org/10.1007/pl00009268
161 rdf:type schema:CreativeWork
162 sg:pub.10.1007/s00285-012-0525-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1009586472
163 https://doi.org/10.1007/s00285-012-0525-x
164 rdf:type schema:CreativeWork
165 sg:pub.10.1007/s00285-016-1084-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034663401
166 https://doi.org/10.1007/s00285-016-1084-3
167 rdf:type schema:CreativeWork
168 sg:pub.10.1007/s00285-018-1260-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105165655
169 https://doi.org/10.1007/s00285-018-1260-8
170 rdf:type schema:CreativeWork
171 sg:pub.10.1007/s00453-017-0330-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085886267
172 https://doi.org/10.1007/s00453-017-0330-4
173 rdf:type schema:CreativeWork
174 sg:pub.10.1007/s10878-017-0111-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1074215713
175 https://doi.org/10.1007/s10878-017-0111-7
176 rdf:type schema:CreativeWork
177 sg:pub.10.1038/nmeth.3830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009914770
178 https://doi.org/10.1038/nmeth.3830
179 rdf:type schema:CreativeWork
180 sg:pub.10.1038/nrg1659 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041578587
181 https://doi.org/10.1038/nrg1659
182 rdf:type schema:CreativeWork
183 sg:pub.10.1186/1471-2105-12-124 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021782995
184 https://doi.org/10.1186/1471-2105-12-124
185 rdf:type schema:CreativeWork
186 sg:pub.10.1186/1471-2105-13-s19-s6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083681507
187 https://doi.org/10.1186/1471-2105-13-s19-s6
188 rdf:type schema:CreativeWork
189 sg:pub.10.1186/1471-2164-15-s6-s12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022056400
190 https://doi.org/10.1186/1471-2164-15-s6-s12
191 rdf:type schema:CreativeWork
192 sg:pub.10.1186/s13015-016-0067-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024877337
193 https://doi.org/10.1186/s13015-016-0067-7
194 rdf:type schema:CreativeWork
195 sg:pub.10.1186/s13015-017-0096-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1084251763
196 https://doi.org/10.1186/s13015-017-0096-x
197 rdf:type schema:CreativeWork
198 sg:pub.10.1186/s13015-017-0114-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1091371079
199 https://doi.org/10.1186/s13015-017-0114-z
200 rdf:type schema:CreativeWork
201 https://app.dimensions.ai/details/publication/pub.1074273155 schema:CreativeWork
202 https://doi.org/10.1006/aama.1995.1020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008822253
203 rdf:type schema:CreativeWork
204 https://doi.org/10.1006/jmbi.1998.2144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002190651
205 rdf:type schema:CreativeWork
206 https://doi.org/10.1016/0012-365x(73)90109-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1012351613
207 rdf:type schema:CreativeWork
208 https://doi.org/10.1016/0020-0190(95)00165-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037202960
209 rdf:type schema:CreativeWork
210 https://doi.org/10.1016/0167-6423(89)90039-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001431838
211 rdf:type schema:CreativeWork
212 https://doi.org/10.1016/j.dam.2006.03.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015244524
213 rdf:type schema:CreativeWork
214 https://doi.org/10.1016/j.gpb.2017.07.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092636759
215 rdf:type schema:CreativeWork
216 https://doi.org/10.1016/j.mbs.2006.11.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005909688
217 rdf:type schema:CreativeWork
218 https://doi.org/10.1016/j.tcs.2014.10.045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015472719
219 rdf:type schema:CreativeWork
220 https://doi.org/10.1016/s0166-218x(02)00250-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046361339
221 rdf:type schema:CreativeWork
222 https://doi.org/10.1073/pnas.1412770112 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025894422
223 rdf:type schema:CreativeWork
224 https://doi.org/10.1073/pnas.96.6.2896 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023469671
225 rdf:type schema:CreativeWork
226 https://doi.org/10.1093/bioinformatics/btg213 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046587046
227 rdf:type schema:CreativeWork
228 https://doi.org/10.1093/bioinformatics/btm585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050090819
229 rdf:type schema:CreativeWork
230 https://doi.org/10.1093/bioinformatics/btx229 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085320664
231 rdf:type schema:CreativeWork
232 https://doi.org/10.1093/gbe/evs100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039510355
233 rdf:type schema:CreativeWork
234 https://doi.org/10.1093/gbe/evt132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051400194
235 rdf:type schema:CreativeWork
236 https://doi.org/10.1093/nar/gkr308 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002392993
237 rdf:type schema:CreativeWork
238 https://doi.org/10.1093/oxfordjournals.molbev.a003907 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040067893
239 rdf:type schema:CreativeWork
240 https://doi.org/10.1111/j.1558-5646.1989.tb04263.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1085729742
241 rdf:type schema:CreativeWork
242 https://doi.org/10.1126/science.278.5338.631 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039646901
243 rdf:type schema:CreativeWork
244 https://doi.org/10.1137/0201008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841171
245 rdf:type schema:CreativeWork
246 https://doi.org/10.1137/0210030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841583
247 rdf:type schema:CreativeWork
248 https://doi.org/10.1137/0213024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841758
249 rdf:type schema:CreativeWork
250 https://doi.org/10.1137/0217079 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842098
251 rdf:type schema:CreativeWork
252 https://doi.org/10.1137/1.9781611973006.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088800965
253 rdf:type schema:CreativeWork
254 https://doi.org/10.1371/journal.pcbi.1000262 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005269052
255 rdf:type schema:CreativeWork
256 https://doi.org/10.1371/journal.pone.0105015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011835816
257 rdf:type schema:CreativeWork
258 https://doi.org/10.4064/fm-70-1-59-101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091799716
259 rdf:type schema:CreativeWork
260 https://www.grid.ac/institutes/grid.11749.3a schema:alternateName Saarland University
261 schema:name Center for Bioinformatics, Saarland University, Building E 2.1, P.O. Box 151150, 66041, Saarbrücken, Germany.
262 Institute of Mathematics and Computer Science, University of Greifswald, Walther-Rathenau-Straße 47, 17487, Greifswald, Germany.
263 rdf:type schema:Organization
264 https://www.grid.ac/institutes/grid.209665.e schema:alternateName Santa Fe Institute
265 schema:name Bioinformatics Group, Department of Computer Science, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
266 Competence Center for Scalable Data Services and Solutions, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
267 Facultad de Ciencias, Universidad National de Colombia, Sede Bogotá, Colombia. studla@bioinf.uni-leipzig.de.
268 German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
269 Institute of Theoretical Chemistry, University of Vienna, Währingerstraße 17, 1090, Vienna, Austria. studla@bioinf.uni-leipzig.de.
270 Interdisciplinary Center of Bioinformatics, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
271 Leipzig Research Center for Civilization Diseases, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
272 Max-Planck-Institute for Mathematics in the Sciences, Inselstraße 22, 04103, Leipzig, Germany. studla@bioinf.uni-leipzig.de.
273 Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM, 87501, USA. studla@bioinf.uni-leipzig.de.
274 rdf:type schema:Organization
275 https://www.grid.ac/institutes/grid.412851.b schema:alternateName Autonomous University of Aguascalientes
276 schema:name Centro de Ciencias Básicas, Universidad Autónoma de Aguascalientes, Av. Universidad 940, 20131, Aguascalientes, AGS, Mexico.
277 Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico.
278 rdf:type schema:Organization
279 https://www.grid.ac/institutes/grid.419532.8 schema:alternateName Max Planck Institute for Mathematics in the Sciences
280 schema:name Max-Planck-Institute for Mathematics in the Sciences, Inselstraße 22, 04103, Leipzig, Germany.
281 rdf:type schema:Organization
282 https://www.grid.ac/institutes/grid.9647.c schema:alternateName Leipzig University
283 schema:name Bioinformatics Group, Department of Computer Science, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany.
284 Interdisciplinary Center of Bioinformatics, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany.
285 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...