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 Nef0bc10c988f45a596cff1c17a0532d4
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 N50c051d423af484f880bf991d5fc0273
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf N679e3b5335a34c17a82c9110a3634cf1
24 schema:name Multiple Genome Alignment: Chaining Algorithms Revisited
25 schema:pagination 1-16
26 schema:productId N17a3761089314c10abe98e2155298230
27 N54d29e5517774162887cfd10564bce21
28 Nd7caf31310d248438a95335d72fa6e82
29 schema:publisher Nf12514b047c648a8acea7ff7d663a37e
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 N6232cd5b8fbb47f4be197681477c51f0
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 N17a3761089314c10abe98e2155298230 schema:name dimensions_id
40 schema:value pub.1022793632
41 rdf:type schema:PropertyValue
42 N50c051d423af484f880bf991d5fc0273 rdf:first Ne99a4dd810ea46b2be7d0d98e5407999
43 rdf:rest N8b593f02b8084b9db83c7255fe2ac773
44 N54d29e5517774162887cfd10564bce21 schema:name doi
45 schema:value 10.1007/3-540-44888-8_1
46 rdf:type schema:PropertyValue
47 N6232cd5b8fbb47f4be197681477c51f0 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N679e3b5335a34c17a82c9110a3634cf1 schema:isbn 978-3-540-40311-1
50 978-3-540-44888-4
51 schema:name Combinatorial Pattern Matching
52 rdf:type schema:Book
53 N6812089e02914cf69c5d500a21c1cb3a rdf:first Nf0bafd01206d44fea0dff7f705b24fa6
54 rdf:rest rdf:nil
55 N8b593f02b8084b9db83c7255fe2ac773 rdf:first Nd1d0354ee3c349fda568ee40219a09a8
56 rdf:rest N6812089e02914cf69c5d500a21c1cb3a
57 Nd0e2f9d17caa42cda445c3dc61a01e06 rdf:first sg:person.07535656415.00
58 rdf:rest rdf:nil
59 Nd1d0354ee3c349fda568ee40219a09a8 schema:familyName Chávez
60 schema:givenName Edgar
61 rdf:type schema:Person
62 Nd7caf31310d248438a95335d72fa6e82 schema:name readcube_id
63 schema:value 6c982a59b50fab84013fdf870267a51cefa25ff833f1b0be17c95840ad2302ac
64 rdf:type schema:PropertyValue
65 Ne99a4dd810ea46b2be7d0d98e5407999 schema:familyName Baeza-Yates
66 schema:givenName Ricardo
67 rdf:type schema:Person
68 Nef0bc10c988f45a596cff1c17a0532d4 rdf:first sg:person.01055007277.44
69 rdf:rest Nd0e2f9d17caa42cda445c3dc61a01e06
70 Nf0bafd01206d44fea0dff7f705b24fa6 schema:familyName Crochemore
71 schema:givenName Maxime
72 rdf:type schema:Person
73 Nf12514b047c648a8acea7ff7d663a37e schema:location Berlin, Heidelberg
74 schema:name Springer Berlin Heidelberg
75 rdf:type schema:Organisation
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)


...