1.375-Approximation Algorithm for Sorting by Reversals View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-08-29

AUTHORS

Piotr Berman , Sridhar Hannenhalli , Marek Karpinski

ABSTRACT

Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem. More... »

PAGES

200-210

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45749-6_21

DOI

http://dx.doi.org/10.1007/3-540-45749-6_21

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and Engineering, The Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science and Engineering, The Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Celera Genomics Co., 45 W. Gude Dr., 20350, Rockville, MD", 
          "id": "http://www.grid.ac/institutes/grid.418124.a", 
          "name": [
            "Celera Genomics Co., 45 W. Gude Dr., 20350, Rockville, MD"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hannenhalli", 
        "givenName": "Sridhar", 
        "id": "sg:person.01341565477.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01341565477.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept. of Computer Science, University of Bonn, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-08-29", 
    "datePublishedReg": "2002-08-29", 
    "description": "Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem.", 
    "editor": [
      {
        "familyName": "M\u00f6hring", 
        "givenName": "Rolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Raman", 
        "givenName": "Rajeev", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45749-6_21", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-44180-9", 
        "978-3-540-45749-7"
      ], 
      "name": "Algorithms \u2014 ESA 2002", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time algorithm", 
      "approximation algorithm", 
      "general combinatorial problems", 
      "time algorithm", 
      "first exact polynomial time algorithm", 
      "new approximation algorithm", 
      "exact polynomial-time algorithm", 
      "combinatorial problems", 
      "special case", 
      "cycle decomposition", 
      "minimum number", 
      "algorithm", 
      "permutations", 
      "breakpoint graph", 
      "problem", 
      "performance ratio", 
      "unsigned permutations", 
      "graph", 
      "Hannenhalli", 
      "Pevzner", 
      "inversion", 
      "decomposition", 
      "preliminary results", 
      "number", 
      "analysis of genomes", 
      "reversal", 
      "cases", 
      "results", 
      "analysis", 
      "series", 
      "ratio", 
      "Christie", 
      "genome", 
      "paper"
    ], 
    "name": "1.375-Approximation Algorithm for Sorting by Reversals", 
    "pagination": "200-210", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016605518"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45749-6_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45749-6_21", 
      "https://app.dimensions.ai/details/publication/pub.1016605518"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_92.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45749-6_21"
  }
]
 

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-45749-6_21'

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-45749-6_21'

Turtle is a human-readable linked data format.

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

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-45749-6_21'


 

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

118 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45749-6_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N11b2693c400641a086f324b2c6521fc8
4 schema:datePublished 2002-08-29
5 schema:datePublishedReg 2002-08-29
6 schema:description Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem.
7 schema:editor Neabedcec67104d1da0ecc78eb71628e3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N99511ec459564ad59e75acfd53824899
11 schema:keywords Christie
12 Hannenhalli
13 Pevzner
14 algorithm
15 analysis
16 analysis of genomes
17 approximation algorithm
18 breakpoint graph
19 cases
20 combinatorial problems
21 cycle decomposition
22 decomposition
23 exact polynomial-time algorithm
24 first exact polynomial time algorithm
25 general combinatorial problems
26 genome
27 graph
28 inversion
29 minimum number
30 new approximation algorithm
31 number
32 paper
33 performance ratio
34 permutations
35 polynomial time algorithm
36 preliminary results
37 problem
38 ratio
39 results
40 reversal
41 series
42 special case
43 time algorithm
44 unsigned permutations
45 schema:name 1.375-Approximation Algorithm for Sorting by Reversals
46 schema:pagination 200-210
47 schema:productId N911f732f22d74d74b5ce28a0f58ea35e
48 Nac975fb18f0349cc957268b3d1fd2e9a
49 schema:publisher N38b836c215ab4edcb8e1e8f00311d360
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016605518
51 https://doi.org/10.1007/3-540-45749-6_21
52 schema:sdDatePublished 2022-08-04T17:22
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N7633f0267f65402aa020eb5ed418fe13
55 schema:url https://doi.org/10.1007/3-540-45749-6_21
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N0d455ac432ad4cd5a742a22787369ddf schema:familyName Möhring
60 schema:givenName Rolf
61 rdf:type schema:Person
62 N11b2693c400641a086f324b2c6521fc8 rdf:first sg:person.01274506210.27
63 rdf:rest N6d5bfcbe48b34f13a6556def0acc4038
64 N38b836c215ab4edcb8e1e8f00311d360 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N3edcbd77d9ac41e4a5267d01779a5655 rdf:first sg:person.011636042271.02
67 rdf:rest rdf:nil
68 N6d5bfcbe48b34f13a6556def0acc4038 rdf:first sg:person.01341565477.18
69 rdf:rest N3edcbd77d9ac41e4a5267d01779a5655
70 N7633f0267f65402aa020eb5ed418fe13 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N911f732f22d74d74b5ce28a0f58ea35e schema:name doi
73 schema:value 10.1007/3-540-45749-6_21
74 rdf:type schema:PropertyValue
75 N99511ec459564ad59e75acfd53824899 schema:isbn 978-3-540-44180-9
76 978-3-540-45749-7
77 schema:name Algorithms — ESA 2002
78 rdf:type schema:Book
79 N9e5f1bfc54e4446d83f9a8a9630962a2 rdf:first Nd5826a11ae6241e28d1974cc7e91f88c
80 rdf:rest rdf:nil
81 Nac975fb18f0349cc957268b3d1fd2e9a schema:name dimensions_id
82 schema:value pub.1016605518
83 rdf:type schema:PropertyValue
84 Nd5826a11ae6241e28d1974cc7e91f88c schema:familyName Raman
85 schema:givenName Rajeev
86 rdf:type schema:Person
87 Neabedcec67104d1da0ecc78eb71628e3 rdf:first N0d455ac432ad4cd5a742a22787369ddf
88 rdf:rest N9e5f1bfc54e4446d83f9a8a9630962a2
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
93 schema:name Computation Theory and Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.011636042271.02 schema:affiliation grid-institutes:None
96 schema:familyName Karpinski
97 schema:givenName Marek
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
99 rdf:type schema:Person
100 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
101 schema:familyName Berman
102 schema:givenName Piotr
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
104 rdf:type schema:Person
105 sg:person.01341565477.18 schema:affiliation grid-institutes:grid.418124.a
106 schema:familyName Hannenhalli
107 schema:givenName Sridhar
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01341565477.18
109 rdf:type schema:Person
110 grid-institutes:None schema:alternateName Dept. of Computer Science, University of Bonn, USA
111 schema:name Dept. of Computer Science, University of Bonn, USA
112 rdf:type schema:Organization
113 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science and Engineering, The Pennsylvania State University, USA
114 schema:name Dept. of Computer Science and Engineering, The Pennsylvania State University, USA
115 rdf:type schema:Organization
116 grid-institutes:grid.418124.a schema:alternateName Celera Genomics Co., 45 W. Gude Dr., 20350, Rockville, MD
117 schema:name Celera Genomics Co., 45 W. Gude Dr., 20350, Rockville, MD
118 rdf:type schema:Organization
 




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


...