Multiple Genome Alignment: Chaining Algorithms Revisited View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Mohamed Ibrahim Abouelhoda , Enno Ohlebusch

ABSTRACT

Given n fragments from k > 2 genomes, we will show how to find an optimal chain of colinear non-overlapping fragments in time O(n log k−2 n log log n) and space O(n log k−2 n). Our result solves an open problem posed by Myers and Miller because it reduces the time complexity of their algorithm by a factor log2 n / log log n and the space complexity by a factor log n. For k = 2 genomes, our algorithm takes O(n log n) time and O(n) space. More... »

PAGES

1-16

References to SciGraph publications

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-540-40311-1
978-3-540-44888-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44888-8_1

DOI

http://dx.doi.org/10.1007/3-540-44888-8_1

DIMENSIONS

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


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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bielefeld University", 
          "id": "https://www.grid.ac/institutes/grid.7491.b", 
          "name": [
            "Faculty of Technology, University of Bielefeld, P.O. Box 10 01 31, 33501\u00a0Bielefeld, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Abouelhoda", 
        "givenName": "Mohamed Ibrahim", 
        "id": "sg:person.01055007277.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01055007277.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Faculty of Computer Science, University of Ulm, Albert-Einstein-Allee, 89069\u00a0Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ohlebusch", 
        "givenName": "Enno", 
        "id": "sg:person.07535656415.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07535656415.00"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(83)90045-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010191688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/16.10.948", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011247050"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(91)90938-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011921257"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.93.17.9061", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027494985"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(77)90031-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029510709"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/17.5.391", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029618543"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1101/gr.10.4.577", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033240051"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01786986", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043049777", 
          "https://doi.org/10.1007/bf01786986"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01786986", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043049777", 
          "https://doi.org/10.1007/bf01786986"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/146637.146650", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048922182"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/30.11.2478", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049218865"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214019", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841808"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0217026", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842045"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "Given n fragments from k > 2 genomes, we will show how to find an optimal chain of colinear non-overlapping fragments in time O(n log k\u22122 n log log n) and space O(n log k\u22122 n). Our result solves an open problem posed by Myers and Miller because it reduces the time complexity of their algorithm by a factor log2 n / log log n and the space complexity by a factor log n. For k = 2 genomes, our algorithm takes O(n log n) time and O(n) space.", 
    "editor": [
      {
        "familyName": "Baeza-Yates", 
        "givenName": "Ricardo", 
        "type": "Person"
      }, 
      {
        "familyName": "Ch\u00e1vez", 
        "givenName": "Edgar", 
        "type": "Person"
      }, 
      {
        "familyName": "Crochemore", 
        "givenName": "Maxime", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44888-8_1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40311-1", 
        "978-3-540-44888-4"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "name": "Multiple Genome Alignment: Chaining Algorithms Revisited", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44888-8_1"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6c982a59b50fab84013fdf870267a51cefa25ff833f1b0be17c95840ad2302ac"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022793632"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44888-8_1", 
      "https://app.dimensions.ai/details/publication/pub.1022793632"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:51", 
    "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_8697_00000257.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44888-8_1"
  }
]
 

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-44888-8_1'

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-44888-8_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44888-8_1'

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-44888-8_1'


 

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

122 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44888-8_1 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N38def915719146dea16d632fab9f54d0
4 schema:citation sg:pub.10.1007/bf01786986
5 https://doi.org/10.1016/0020-0190(77)90031-x
6 https://doi.org/10.1016/0020-0190(83)90045-5
7 https://doi.org/10.1016/0022-2836(91)90938-3
8 https://doi.org/10.1073/pnas.93.17.9061
9 https://doi.org/10.1093/bioinformatics/16.10.948
10 https://doi.org/10.1093/bioinformatics/17.5.391
11 https://doi.org/10.1093/nar/30.11.2478
12 https://doi.org/10.1101/gr.10.4.577
13 https://doi.org/10.1137/0214019
14 https://doi.org/10.1137/0217026
15 https://doi.org/10.1145/146637.146650
16 schema:datePublished 2003
17 schema:datePublishedReg 2003-01-01
18 schema:description Given n fragments from k > 2 genomes, we will show how to find an optimal chain of colinear non-overlapping fragments in time O(n log k−2 n log log n) and space O(n log k−2 n). Our result solves an open problem posed by Myers and Miller because it reduces the time complexity of their algorithm by a factor log2 n / log log n and the space complexity by a factor log n. For k = 2 genomes, our algorithm takes O(n log n) time and O(n) space.
19 schema:editor N1ca4fe153819426bb70920e0fe0e72ea
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf N4bbf5f08357f4071a59be6cd575001bb
24 schema:name Multiple Genome Alignment: Chaining Algorithms Revisited
25 schema:pagination 1-16
26 schema:productId N4e2bcdf5011d42b5a638f1ca4052f1d2
27 N9d148f3ed96c454287e02c39c6f3b6a6
28 Nd3c018d088d94a99a303ffada41599dc
29 schema:publisher N96ffa9a486b745df9768a2288f12ec5a
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022793632
31 https://doi.org/10.1007/3-540-44888-8_1
32 schema:sdDatePublished 2019-04-15T23:51
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N38af577bc9c047258fd0e9421c177cba
35 schema:url http://link.springer.com/10.1007/3-540-44888-8_1
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N1ca4fe153819426bb70920e0fe0e72ea rdf:first Nab6b8418aadf4f4083e6b89c5c470755
40 rdf:rest Nd0bdbae5ec3f4d8e8ad7546275e8790f
41 N38af577bc9c047258fd0e9421c177cba schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N38def915719146dea16d632fab9f54d0 rdf:first sg:person.01055007277.44
44 rdf:rest Nde4b2302fb67410c8a573d615e7462a5
45 N4bbf5f08357f4071a59be6cd575001bb schema:isbn 978-3-540-40311-1
46 978-3-540-44888-4
47 schema:name Combinatorial Pattern Matching
48 rdf:type schema:Book
49 N4e2bcdf5011d42b5a638f1ca4052f1d2 schema:name doi
50 schema:value 10.1007/3-540-44888-8_1
51 rdf:type schema:PropertyValue
52 N96ffa9a486b745df9768a2288f12ec5a schema:location Berlin, Heidelberg
53 schema:name Springer Berlin Heidelberg
54 rdf:type schema:Organisation
55 N9d148f3ed96c454287e02c39c6f3b6a6 schema:name dimensions_id
56 schema:value pub.1022793632
57 rdf:type schema:PropertyValue
58 Nab6b8418aadf4f4083e6b89c5c470755 schema:familyName Baeza-Yates
59 schema:givenName Ricardo
60 rdf:type schema:Person
61 Nb020799398e74519bdc96cbebbee1f1e schema:familyName Crochemore
62 schema:givenName Maxime
63 rdf:type schema:Person
64 Nc2b30ac3bb414a1d9384b9095983b885 rdf:first Nb020799398e74519bdc96cbebbee1f1e
65 rdf:rest rdf:nil
66 Ncf2cde3ce3dd4066b7335fae8c8d1d4a schema:familyName Chávez
67 schema:givenName Edgar
68 rdf:type schema:Person
69 Nd0bdbae5ec3f4d8e8ad7546275e8790f rdf:first Ncf2cde3ce3dd4066b7335fae8c8d1d4a
70 rdf:rest Nc2b30ac3bb414a1d9384b9095983b885
71 Nd3c018d088d94a99a303ffada41599dc schema:name readcube_id
72 schema:value 6c982a59b50fab84013fdf870267a51cefa25ff833f1b0be17c95840ad2302ac
73 rdf:type schema:PropertyValue
74 Nde4b2302fb67410c8a573d615e7462a5 rdf:first sg:person.07535656415.00
75 rdf:rest rdf:nil
76 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
77 schema:name Psychology and Cognitive Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
80 schema:name Psychology
81 rdf:type schema:DefinedTerm
82 sg:person.01055007277.44 schema:affiliation https://www.grid.ac/institutes/grid.7491.b
83 schema:familyName Abouelhoda
84 schema:givenName Mohamed Ibrahim
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01055007277.44
86 rdf:type schema:Person
87 sg:person.07535656415.00 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
88 schema:familyName Ohlebusch
89 schema:givenName Enno
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07535656415.00
91 rdf:type schema:Person
92 sg:pub.10.1007/bf01786986 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043049777
93 https://doi.org/10.1007/bf01786986
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0020-0190(77)90031-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1029510709
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/0020-0190(83)90045-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010191688
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0022-2836(91)90938-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011921257
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1073/pnas.93.17.9061 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027494985
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1093/bioinformatics/16.10.948 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011247050
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1093/bioinformatics/17.5.391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029618543
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1093/nar/30.11.2478 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049218865
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1101/gr.10.4.577 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033240051
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0214019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841808
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1137/0217026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842045
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/146637.146650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048922182
116 rdf:type schema:CreativeWork
117 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
118 schema:name Faculty of Computer Science, University of Ulm, Albert-Einstein-Allee, 89069 Ulm, Germany
119 rdf:type schema:Organization
120 https://www.grid.ac/institutes/grid.7491.b schema:alternateName Bielefeld University
121 schema:name Faculty of Technology, University of Bielefeld, P.O. Box 10 01 31, 33501 Bielefeld, Germany
122 rdf:type schema:Organization
 




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


...