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": [
      "efficient approximation algorithm", 
      "operations research literature", 
      "scheduling problem", 
      "approximation algorithm", 
      "performance guarantees", 
      "first polynomial time algorithm", 
      "polynomial time algorithm", 
      "non-trivial class", 
      "non-trivial performance guarantees", 
      "maximum possible number", 
      "useful properties", 
      "time algorithm", 
      "main contribution", 
      "algorithm", 
      "possible number", 
      "problem", 
      "tractability results", 
      "minimum number", 
      "novel connection", 
      "guarantees", 
      "model", 
      "instances", 
      "class", 
      "number", 
      "connection", 
      "properties", 
      "structural properties", 
      "distance", 
      "form", 
      "syntenic distance", 
      "results", 
      "literature", 
      "research literature", 
      "questions", 
      "contribution", 
      "fusion", 
      "reduction", 
      "fission", 
      "genome", 
      "species", 
      "synteny", 
      "paper", 
      "translocation", 
      "linear syntenic distance", 
      "general linear synteny problem", 
      "linear synteny problem", 
      "synteny problem", 
      "linear 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-01-01T19:07", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_126.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.

120 TRIPLES      23 PREDICATES      74 URIs      67 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 Nc746b188d14144f883ed46f2d543ef5e
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 N39bd0b98ceb24b5cabc6f571faecb4a0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb99c8de122df4ac7b02c9645132977ce
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 general linear synteny problem
24 genome
25 guarantees
26 instances
27 linear syntenic distance
28 linear synteny
29 linear synteny problem
30 literature
31 main contribution
32 maximum possible number
33 minimum number
34 model
35 non-trivial class
36 non-trivial performance guarantees
37 novel connection
38 number
39 operations research literature
40 paper
41 performance guarantees
42 polynomial time algorithm
43 possible number
44 problem
45 properties
46 questions
47 reduction
48 research literature
49 results
50 scheduling problem
51 species
52 structural properties
53 syntenic distance
54 synteny
55 synteny problem
56 time algorithm
57 tractability results
58 translocation
59 useful properties
60 schema:name Structural Properties and Tractability Results for Linear Synteny
61 schema:pagination 248-263
62 schema:productId N1dcb6fbbb8654642a9881a4e0d1ec6bf
63 Ne57feea0a7c64378b39790c565905fae
64 schema:publisher Nd9627a339a514d388b21b6a43bd445a2
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005695677
66 https://doi.org/10.1007/3-540-45123-4_22
67 schema:sdDatePublished 2022-01-01T19:07
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher Nab4fccc45ad54ddda6c7ebe8bf778cae
70 schema:url https://doi.org/10.1007/3-540-45123-4_22
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N1dcb6fbbb8654642a9881a4e0d1ec6bf schema:name dimensions_id
75 schema:value pub.1005695677
76 rdf:type schema:PropertyValue
77 N39bd0b98ceb24b5cabc6f571faecb4a0 rdf:first N8cf4887d328b4ddea0c330c42791119f
78 rdf:rest Nee8bda4d1c1a44a5ae74d15df064a601
79 N8cf4887d328b4ddea0c330c42791119f schema:familyName Giancarlo
80 schema:givenName Raffaele
81 rdf:type schema:Person
82 N8d872ca9100247feb8c379e9299b6006 schema:familyName Sankoff
83 schema:givenName David
84 rdf:type schema:Person
85 Nab4fccc45ad54ddda6c7ebe8bf778cae schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 Nb99c8de122df4ac7b02c9645132977ce schema:isbn 978-3-540-45123-5
88 978-3-540-67633-1
89 schema:name Combinatorial Pattern Matching
90 rdf:type schema:Book
91 Nc746b188d14144f883ed46f2d543ef5e rdf:first sg:person.01261204147.02
92 rdf:rest Nf92e0fb9207548c0bb68a58940000164
93 Nd9627a339a514d388b21b6a43bd445a2 schema:name Springer Nature
94 rdf:type schema:Organisation
95 Ne57feea0a7c64378b39790c565905fae schema:name doi
96 schema:value 10.1007/3-540-45123-4_22
97 rdf:type schema:PropertyValue
98 Nee8bda4d1c1a44a5ae74d15df064a601 rdf:first N8d872ca9100247feb8c379e9299b6006
99 rdf:rest rdf:nil
100 Nf92e0fb9207548c0bb68a58940000164 rdf:first sg:person.011522233557.04
101 rdf:rest rdf:nil
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
106 schema:name Computation Theory and Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
109 schema:familyName Kleinberg
110 schema:givenName Jon
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
112 rdf:type schema:Person
113 sg:person.01261204147.02 schema:affiliation grid-institutes:grid.5386.8
114 schema:familyName Liben-Nowell
115 schema:givenName David
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01261204147.02
117 rdf:type schema:Person
118 grid-institutes:grid.5386.8 schema:alternateName Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA
119 schema:name Department of Computer Science, Cornell University, 14853, Ithaca, NY, USA
120 rdf:type schema:Organization
 




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


...