Ontology type: schema:Chapter
2000
AUTHORSDavid Liben-Nowell , Jon Kleinberg
ABSTRACTThe 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... »
PAGES248-263
Combinatorial Pattern Matching
ISBN
978-3-540-67633-1
978-3-540-45123-5
http://scigraph.springernature.com/pub.10.1007/3-540-45123-4_22
DOIhttp://dx.doi.org/10.1007/3-540-45123-4_22
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1005695677
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
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 |