Finding an Optimal Inversion Median: Experimental Results View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001

AUTHORS

Adam C. Siepel , Bernard M. E. Moret

ABSTRACT

We derive a branch-and-bound algorithm to find an optimal inversion median of three signed permutations. The algorithm prunes to manageable size an extremely large search tree using simple geometric properties of the problem and a newly available linear-time routine for inversion distance. Our experiments on simulated data sets indicate that the algorithm finds optimal medians in reasonable time for genomes of medium size when distances are not too large, as commonly occurs in phylogeny reconstruction. In addition, we have compared inversion and breakpoint medians, and found that inversion medians generally score significantly better and tend to be far more unique, which should make them valuable in median-based tree-building algorithms. More... »

PAGES

189-203

Book

TITLE

Algorithms in Bioinformatics

ISBN

978-3-540-42516-8
978-3-540-44696-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44696-6_15

DOI

http://dx.doi.org/10.1007/3-540-44696-6_15

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of New Mexico", 
          "id": "https://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "Department of Computer Science, University of New Mexico Albuquerque, NM\u00a087131, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Siepel", 
        "givenName": "Adam C.", 
        "id": "sg:person.0734340315.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0734340315.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of New Mexico", 
          "id": "https://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "Department of Computer Science, University of New Mexico Albuquerque, NM\u00a087131, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moret", 
        "givenName": "Bernard M. E.", 
        "id": "sg:person.012650704576.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012650704576.45"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1073/pnas.89.14.6575", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003414922"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/geno.1995.9873", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016300842"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0378-1119(95)00878-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023060366"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-5193(82)90384-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035278148"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/267521.267883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037861863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/267521.267883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037861863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/332306.332563", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052439269"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/332306.332563", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052439269"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539798334207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880246"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "We derive a branch-and-bound algorithm to find an optimal inversion median of three signed permutations. The algorithm prunes to manageable size an extremely large search tree using simple geometric properties of the problem and a newly available linear-time routine for inversion distance. Our experiments on simulated data sets indicate that the algorithm finds optimal medians in reasonable time for genomes of medium size when distances are not too large, as commonly occurs in phylogeny reconstruction. In addition, we have compared inversion and breakpoint medians, and found that inversion medians generally score significantly better and tend to be far more unique, which should make them valuable in median-based tree-building algorithms.", 
    "editor": [
      {
        "familyName": "Gascuel", 
        "givenName": "Olivier", 
        "type": "Person"
      }, 
      {
        "familyName": "Moret", 
        "givenName": "Bernard M. E.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44696-6_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42516-8", 
        "978-3-540-44696-5"
      ], 
      "name": "Algorithms in Bioinformatics", 
      "type": "Book"
    }, 
    "name": "Finding an Optimal Inversion Median: Experimental Results", 
    "pagination": "189-203", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44696-6_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "263b8c0c4eab7ee4aec4bfc3332f6757b8d287c5512cff3ae88235bb3f2d5f97"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008025068"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44696-6_15", 
      "https://app.dimensions.ai/details/publication/pub.1008025068"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:32", 
    "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/0000000001_0000000264/records_8660_00000248.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44696-6_15"
  }
]
 

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/3-540-44696-6_15'

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/3-540-44696-6_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44696-6_15'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44696-6_15'


 

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

98 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44696-6_15 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N82bc12518b2e4471b3c0704ef044a8c3
4 schema:citation https://doi.org/10.1006/geno.1995.9873
5 https://doi.org/10.1016/0022-5193(82)90384-8
6 https://doi.org/10.1016/0378-1119(95)00878-0
7 https://doi.org/10.1073/pnas.89.14.6575
8 https://doi.org/10.1137/s0097539798334207
9 https://doi.org/10.1145/267521.267883
10 https://doi.org/10.1145/332306.332563
11 schema:datePublished 2001
12 schema:datePublishedReg 2001-01-01
13 schema:description We derive a branch-and-bound algorithm to find an optimal inversion median of three signed permutations. The algorithm prunes to manageable size an extremely large search tree using simple geometric properties of the problem and a newly available linear-time routine for inversion distance. Our experiments on simulated data sets indicate that the algorithm finds optimal medians in reasonable time for genomes of medium size when distances are not too large, as commonly occurs in phylogeny reconstruction. In addition, we have compared inversion and breakpoint medians, and found that inversion medians generally score significantly better and tend to be far more unique, which should make them valuable in median-based tree-building algorithms.
14 schema:editor N1b112bfa143143069e09f21dc139f009
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree true
18 schema:isPartOf N7be299b7a90943ed9ebd81946c418b3a
19 schema:name Finding an Optimal Inversion Median: Experimental Results
20 schema:pagination 189-203
21 schema:productId N1c5b677450d6451ea5a42d9fbba156d6
22 N5ae6ae3dd9424940a86ee28f1581b3af
23 N7d6975ffe9dc454c99f9024bb04735be
24 schema:publisher Na8921bd623f3476a858a884d036ed369
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008025068
26 https://doi.org/10.1007/3-540-44696-6_15
27 schema:sdDatePublished 2019-04-15T11:32
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N83838b7dcbaf4063b7c8380a830febbf
30 schema:url http://link.springer.com/10.1007/3-540-44696-6_15
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N08958f3fdcd64b17b6003121fea593a2 rdf:first sg:person.012650704576.45
35 rdf:rest rdf:nil
36 N1b112bfa143143069e09f21dc139f009 rdf:first N27c339fd2ee94847a950fabff4ee667b
37 rdf:rest N2b67e277e35142a6a7cb3602d61f3fbc
38 N1c5b677450d6451ea5a42d9fbba156d6 schema:name readcube_id
39 schema:value 263b8c0c4eab7ee4aec4bfc3332f6757b8d287c5512cff3ae88235bb3f2d5f97
40 rdf:type schema:PropertyValue
41 N27c339fd2ee94847a950fabff4ee667b schema:familyName Gascuel
42 schema:givenName Olivier
43 rdf:type schema:Person
44 N2b67e277e35142a6a7cb3602d61f3fbc rdf:first Nb9ab644da1df463b8900b3c71e2f7c50
45 rdf:rest rdf:nil
46 N5ae6ae3dd9424940a86ee28f1581b3af schema:name doi
47 schema:value 10.1007/3-540-44696-6_15
48 rdf:type schema:PropertyValue
49 N7be299b7a90943ed9ebd81946c418b3a schema:isbn 978-3-540-42516-8
50 978-3-540-44696-5
51 schema:name Algorithms in Bioinformatics
52 rdf:type schema:Book
53 N7d6975ffe9dc454c99f9024bb04735be schema:name dimensions_id
54 schema:value pub.1008025068
55 rdf:type schema:PropertyValue
56 N82bc12518b2e4471b3c0704ef044a8c3 rdf:first sg:person.0734340315.34
57 rdf:rest N08958f3fdcd64b17b6003121fea593a2
58 N83838b7dcbaf4063b7c8380a830febbf schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 Na8921bd623f3476a858a884d036ed369 schema:location Berlin, Heidelberg
61 schema:name Springer Berlin Heidelberg
62 rdf:type schema:Organisation
63 Nb9ab644da1df463b8900b3c71e2f7c50 schema:familyName Moret
64 schema:givenName Bernard M. E.
65 rdf:type schema:Person
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
70 schema:name Artificial Intelligence and Image Processing
71 rdf:type schema:DefinedTerm
72 sg:person.012650704576.45 schema:affiliation https://www.grid.ac/institutes/grid.266832.b
73 schema:familyName Moret
74 schema:givenName Bernard M. E.
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012650704576.45
76 rdf:type schema:Person
77 sg:person.0734340315.34 schema:affiliation https://www.grid.ac/institutes/grid.266832.b
78 schema:familyName Siepel
79 schema:givenName Adam C.
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0734340315.34
81 rdf:type schema:Person
82 https://doi.org/10.1006/geno.1995.9873 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016300842
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1016/0022-5193(82)90384-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035278148
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1016/0378-1119(95)00878-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023060366
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1073/pnas.89.14.6575 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003414922
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1137/s0097539798334207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880246
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1145/267521.267883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037861863
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1145/332306.332563 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052439269
95 rdf:type schema:CreativeWork
96 https://www.grid.ac/institutes/grid.266832.b schema:alternateName University of New Mexico
97 schema:name Department of Computer Science, University of New Mexico Albuquerque, NM 87131, USA
98 rdf:type schema:Organization
 




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


...