Structural Properties and Tractability Results for Linear Synteny View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

David Liben-Nowell , Jon Kleinberg

ABSTRACT

The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature. More... »

PAGES

248-263

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-540-67633-1
978-3-540-45123-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45123-4_22

DOI

http://dx.doi.org/10.1007/3-540-45123-4_22

DIMENSIONS

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


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": "Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liben-Nowell", 
        "givenName": "David", 
        "id": "sg:person.01261204147.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01261204147.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleinberg", 
        "givenName": "Jon", 
        "id": "sg:person.011522233557.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature.", 
    "editor": [
      {
        "familyName": "Giancarlo", 
        "givenName": "Raffaele", 
        "type": "Person"
      }, 
      {
        "familyName": "Sankoff", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45123-4_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67633-1", 
        "978-3-540-45123-5"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "non-trivial performance guarantees", 
      "efficient approximation algorithm", 
      "operations research literature", 
      "syntenic distance", 
      "maximum possible number", 
      "first polynomial-time algorithm", 
      "non-trivial class", 
      "polynomial time algorithm", 
      "scheduling problem", 
      "approximation algorithm", 
      "performance guarantees", 
      "tractability results", 
      "time algorithm", 
      "possible number", 
      "minimum number", 
      "useful properties", 
      "algorithm", 
      "main contribution", 
      "problem", 
      "structural properties", 
      "novel connection", 
      "model", 
      "distance", 
      "instances", 
      "properties", 
      "guarantees", 
      "class", 
      "number", 
      "connection", 
      "form", 
      "results", 
      "contribution", 
      "fission", 
      "literature", 
      "questions", 
      "reduction", 
      "research literature", 
      "fusion", 
      "species", 
      "genome", 
      "paper", 
      "translocation", 
      "synteny"
    ], 
    "name": "Structural Properties and Tractability Results for Linear Synteny", 
    "pagination": "248-263", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005695677"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45123-4_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45123-4_22", 
      "https://app.dimensions.ai/details/publication/pub.1005695677"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_231.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45123-4_22"
  }
]
 

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-45123-4_22'

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-45123-4_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45123-4_22'

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-45123-4_22'


 

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

115 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45123-4_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N0ef3cd0186ab45f692bdbbc2b49b9feb
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature.
7 schema:editor N0d138959625040a095402295fd37fa5c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nee4fb7fe21864e689a372fe5661ff92a
12 schema:keywords algorithm
13 approximation algorithm
14 class
15 connection
16 contribution
17 distance
18 efficient approximation algorithm
19 first polynomial-time algorithm
20 fission
21 form
22 fusion
23 genome
24 guarantees
25 instances
26 literature
27 main contribution
28 maximum possible number
29 minimum number
30 model
31 non-trivial class
32 non-trivial performance guarantees
33 novel connection
34 number
35 operations research literature
36 paper
37 performance guarantees
38 polynomial time algorithm
39 possible number
40 problem
41 properties
42 questions
43 reduction
44 research literature
45 results
46 scheduling problem
47 species
48 structural properties
49 syntenic distance
50 synteny
51 time algorithm
52 tractability results
53 translocation
54 useful properties
55 schema:name Structural Properties and Tractability Results for Linear Synteny
56 schema:pagination 248-263
57 schema:productId N0e93cf18dc784b748e1aa767eb561192
58 Na687ea4964264374bb1561bd86a103f1
59 schema:publisher N5d3e0cc170004f20a15c0e66e5ac7aff
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005695677
61 https://doi.org/10.1007/3-540-45123-4_22
62 schema:sdDatePublished 2022-05-20T07:44
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N40f6716fcf4142a69525ae57418d365b
65 schema:url https://doi.org/10.1007/3-540-45123-4_22
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N0d138959625040a095402295fd37fa5c rdf:first N3cc747b2c0984a8ba6c8d27a63de0047
70 rdf:rest Nc32ca13ab6e24ed0afb7ed3e05d8d9b1
71 N0e93cf18dc784b748e1aa767eb561192 schema:name dimensions_id
72 schema:value pub.1005695677
73 rdf:type schema:PropertyValue
74 N0ef3cd0186ab45f692bdbbc2b49b9feb rdf:first sg:person.01261204147.02
75 rdf:rest Nbe37286066fe4fcaa6fc80e1fb464256
76 N3cc747b2c0984a8ba6c8d27a63de0047 schema:familyName Giancarlo
77 schema:givenName Raffaele
78 rdf:type schema:Person
79 N40f6716fcf4142a69525ae57418d365b schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N5d3e0cc170004f20a15c0e66e5ac7aff schema:name Springer Nature
82 rdf:type schema:Organisation
83 Na687ea4964264374bb1561bd86a103f1 schema:name doi
84 schema:value 10.1007/3-540-45123-4_22
85 rdf:type schema:PropertyValue
86 Nbe37286066fe4fcaa6fc80e1fb464256 rdf:first sg:person.011522233557.04
87 rdf:rest rdf:nil
88 Nc32ca13ab6e24ed0afb7ed3e05d8d9b1 rdf:first Ne2a52619c3ca469794c5ee61f91f8dd4
89 rdf:rest rdf:nil
90 Ne2a52619c3ca469794c5ee61f91f8dd4 schema:familyName Sankoff
91 schema:givenName David
92 rdf:type schema:Person
93 Nee4fb7fe21864e689a372fe5661ff92a schema:isbn 978-3-540-45123-5
94 978-3-540-67633-1
95 schema:name Combinatorial Pattern Matching
96 rdf:type schema:Book
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
104 schema:familyName Kleinberg
105 schema:givenName Jon
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
107 rdf:type schema:Person
108 sg:person.01261204147.02 schema:affiliation grid-institutes:grid.5386.8
109 schema:familyName Liben-Nowell
110 schema:givenName David
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01261204147.02
112 rdf:type schema:Person
113 grid-institutes:grid.5386.8 schema:alternateName Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA
114 schema:name Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA
115 rdf:type schema:Organization
 




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


...