The Bottleneck Tree Alignment Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Yen Hung Chen , Chuan Yi Tang

ABSTRACT

Given a set W of k sequences (strings) and a tree structure T with k leaves, each of which is labeled with a unique sequence in W, a tree alignment is to label a sequence to each internal node of T. The weight of an edge of the tree alignment is the distance, such as Hamming distance, Levenshtein (edit) distance or reversal distance, between the two sequences labeled to the two ends of the edge. The bottleneck tree alignment problem is to find a tree alignment such that the weight of the largest edge is minimized. A lifted tree alignment is a tree alignment, where each internal node v is labeled one of the sequences that was labeled to the children of v. The bottleneck lifted tree alignment problem is to find a lifted tree alignment such that the weight of the largest edge is minimized. In this paper, we show that the bottleneck tree alignment problem is NP-complete even when the tree structure is the binary tree and the weight function is metric. For special cases, we present an exact algorithm to solve the bottleneck lifted tree alignment problem in polynomial time. If the weight function is ultrametric, we show that any lifted tree alignment is an optimal bottleneck tree alignment. More... »

PAGES

631-637

References to SciGraph publications

Book

TITLE

Computational Science and Its Applications - ICCSA 2006

ISBN

978-3-540-34075-1
978-3-540-34076-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11751595_67

DOI

http://dx.doi.org/10.1007/11751595_67

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National University of Kaohsiung", 
          "id": "https://www.grid.ac/institutes/grid.412111.6", 
          "name": [
            "Department of Applied Mathematics, National University of Kaohsiung, 811, Kaohsiung, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Yen Hung", 
        "id": "sg:person.01347725471.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02459635", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007125460", 
          "https://doi.org/10.1007/bf02459635"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02459635", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007125460", 
          "https://doi.org/10.1007/bf02459635"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/b978-0-444-88071-0.50010-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007810942"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(99)00324-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030133750"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(98)00079-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034216725"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1997.0882", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038662866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01955679", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038787545", 
          "https://doi.org/10.1007/bf01955679"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01955679", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038787545", 
          "https://doi.org/10.1007/bf01955679"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009885610075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044701682", 
          "https://doi.org/10.1023/a:1009885610075"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(97)00240-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047421142"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321796.321811", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049170127"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/cmb.1994.1.337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059245085"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0128004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062839274"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539796313507", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880147"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511574931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098674485"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Given a set W of k sequences (strings) and a tree structure T with k leaves, each of which is labeled with a unique sequence in W, a tree alignment is to label a sequence to each internal node of T. The weight of an edge of the tree alignment is the distance, such as Hamming distance, Levenshtein (edit) distance or reversal distance, between the two sequences labeled to the two ends of the edge. The bottleneck tree alignment problem is to find a tree alignment such that the weight of the largest edge is minimized. A lifted tree alignment is a tree alignment, where each internal node v is labeled one of the sequences that was labeled to the children of v. The bottleneck lifted tree alignment problem is to find a lifted tree alignment such that the weight of the largest edge is minimized. In this paper, we show that the bottleneck tree alignment problem is NP-complete even when the tree structure is the binary tree and the weight function is metric. For special cases, we present an exact algorithm to solve the bottleneck lifted tree alignment problem in polynomial time. If the weight function is ultrametric, we show that any lifted tree alignment is an optimal bottleneck tree alignment.", 
    "editor": [
      {
        "familyName": "Gavrilova", 
        "givenName": "Marina", 
        "type": "Person"
      }, 
      {
        "familyName": "Gervasi", 
        "givenName": "Osvaldo", 
        "type": "Person"
      }, 
      {
        "familyName": "Kumar", 
        "givenName": "Vipin", 
        "type": "Person"
      }, 
      {
        "familyName": "Tan", 
        "givenName": "C. J. Kenneth", 
        "type": "Person"
      }, 
      {
        "familyName": "Taniar", 
        "givenName": "David", 
        "type": "Person"
      }, 
      {
        "familyName": "Lagan\u00e1", 
        "givenName": "Antonio", 
        "type": "Person"
      }, 
      {
        "familyName": "Mun", 
        "givenName": "Youngsong", 
        "type": "Person"
      }, 
      {
        "familyName": "Choo", 
        "givenName": "Hyunseung", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11751595_67", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34075-1", 
        "978-3-540-34076-8"
      ], 
      "name": "Computational Science and Its Applications - ICCSA 2006", 
      "type": "Book"
    }, 
    "name": "The Bottleneck Tree Alignment Problems", 
    "pagination": "631-637", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048758676"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11751595_67"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e846e2d2275a8af1668fb9d1dc113bd8dca3dcd00cef8907fcc2241d80304223"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11751595_67", 
      "https://app.dimensions.ai/details/publication/pub.1048758676"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:35", 
    "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/0000000365_0000000365/records_71674_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11751595_67"
  }
]
 

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/11751595_67'

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/11751595_67'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11751595_67'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11751595_67'


 

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

152 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11751595_67 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfee1c6233f464c4e89cf96fd949a9bf1
4 schema:citation sg:pub.10.1007/bf01955679
5 sg:pub.10.1007/bf02459635
6 sg:pub.10.1023/a:1009885610075
7 https://doi.org/10.1006/jagm.1997.0882
8 https://doi.org/10.1016/b978-0-444-88071-0.50010-2
9 https://doi.org/10.1016/s0166-218x(98)00079-1
10 https://doi.org/10.1016/s0304-3975(97)00240-5
11 https://doi.org/10.1016/s0304-3975(99)00324-2
12 https://doi.org/10.1017/cbo9780511574931
13 https://doi.org/10.1089/cmb.1994.1.337
14 https://doi.org/10.1137/0128004
15 https://doi.org/10.1137/s0097539796313507
16 https://doi.org/10.1145/321796.321811
17 schema:datePublished 2006
18 schema:datePublishedReg 2006-01-01
19 schema:description Given a set W of k sequences (strings) and a tree structure T with k leaves, each of which is labeled with a unique sequence in W, a tree alignment is to label a sequence to each internal node of T. The weight of an edge of the tree alignment is the distance, such as Hamming distance, Levenshtein (edit) distance or reversal distance, between the two sequences labeled to the two ends of the edge. The bottleneck tree alignment problem is to find a tree alignment such that the weight of the largest edge is minimized. A lifted tree alignment is a tree alignment, where each internal node v is labeled one of the sequences that was labeled to the children of v. The bottleneck lifted tree alignment problem is to find a lifted tree alignment such that the weight of the largest edge is minimized. In this paper, we show that the bottleneck tree alignment problem is NP-complete even when the tree structure is the binary tree and the weight function is metric. For special cases, we present an exact algorithm to solve the bottleneck lifted tree alignment problem in polynomial time. If the weight function is ultrametric, we show that any lifted tree alignment is an optimal bottleneck tree alignment.
20 schema:editor Nc32bf463780d4728bdebc9a1b34ef2bb
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf N8155b27985df4bc49c25247313a2daa0
25 schema:name The Bottleneck Tree Alignment Problems
26 schema:pagination 631-637
27 schema:productId N2e7ebf8c903a4fac8ed5f45132c2a23b
28 N593804b626fe4870b4b0d862127e9a08
29 N5decdd493049492c881f7e6e3c36c03b
30 schema:publisher N2852c07aab0840a99366ea942ee2459c
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048758676
32 https://doi.org/10.1007/11751595_67
33 schema:sdDatePublished 2019-04-16T08:35
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N66bc8b166c254322bff899e6f7bc5913
36 schema:url https://link.springer.com/10.1007%2F11751595_67
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N12917de64db0489eb0430b4d6648da1d rdf:first N1c367afa2fa441e5a540a81c4a2ef8d7
41 rdf:rest N4821ff3f8ce14e7e92b7720f329505d3
42 N173da1c716a94ad688918fcff71f8dc9 schema:familyName Kumar
43 schema:givenName Vipin
44 rdf:type schema:Person
45 N1ba34eb22e9549509922b55f47db0549 rdf:first Na6519a642d8340849d2bb95b03429729
46 rdf:rest N12917de64db0489eb0430b4d6648da1d
47 N1c367afa2fa441e5a540a81c4a2ef8d7 schema:familyName Mun
48 schema:givenName Youngsong
49 rdf:type schema:Person
50 N2852c07aab0840a99366ea942ee2459c schema:location Berlin, Heidelberg
51 schema:name Springer Berlin Heidelberg
52 rdf:type schema:Organisation
53 N2e7ebf8c903a4fac8ed5f45132c2a23b schema:name doi
54 schema:value 10.1007/11751595_67
55 rdf:type schema:PropertyValue
56 N4821ff3f8ce14e7e92b7720f329505d3 rdf:first N52edfb3af10749ad9d9f85f34000c36f
57 rdf:rest rdf:nil
58 N52edfb3af10749ad9d9f85f34000c36f schema:familyName Choo
59 schema:givenName Hyunseung
60 rdf:type schema:Person
61 N593804b626fe4870b4b0d862127e9a08 schema:name dimensions_id
62 schema:value pub.1048758676
63 rdf:type schema:PropertyValue
64 N5c47e109a29c46d89f045b247909f873 rdf:first N5f9febea5cce46f8a3b72ad83b46514a
65 rdf:rest Nb6e261a832a041e2ac84a4695f894911
66 N5decdd493049492c881f7e6e3c36c03b schema:name readcube_id
67 schema:value e846e2d2275a8af1668fb9d1dc113bd8dca3dcd00cef8907fcc2241d80304223
68 rdf:type schema:PropertyValue
69 N5f9febea5cce46f8a3b72ad83b46514a schema:familyName Gervasi
70 schema:givenName Osvaldo
71 rdf:type schema:Person
72 N66bc8b166c254322bff899e6f7bc5913 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N6c953ed31b65414c9b8df27fc410dd26 schema:familyName Taniar
75 schema:givenName David
76 rdf:type schema:Person
77 N8155b27985df4bc49c25247313a2daa0 schema:isbn 978-3-540-34075-1
78 978-3-540-34076-8
79 schema:name Computational Science and Its Applications - ICCSA 2006
80 rdf:type schema:Book
81 N98693c32155e4945a2547f6b9aa5796c rdf:first sg:person.01312526135.27
82 rdf:rest rdf:nil
83 Na6519a642d8340849d2bb95b03429729 schema:familyName Lagan√°
84 schema:givenName Antonio
85 rdf:type schema:Person
86 Naa2564df04c64c8e8b96700f8fae48ce rdf:first Nd36eb893bcb04517bc42c1cce8379569
87 rdf:rest Ne7604879a61043fc81f334ebbb569c90
88 Nb6e261a832a041e2ac84a4695f894911 rdf:first N173da1c716a94ad688918fcff71f8dc9
89 rdf:rest Naa2564df04c64c8e8b96700f8fae48ce
90 Nbeeb7e10990840d48c1cacf9327680eb schema:familyName Gavrilova
91 schema:givenName Marina
92 rdf:type schema:Person
93 Nc32bf463780d4728bdebc9a1b34ef2bb rdf:first Nbeeb7e10990840d48c1cacf9327680eb
94 rdf:rest N5c47e109a29c46d89f045b247909f873
95 Nd36eb893bcb04517bc42c1cce8379569 schema:familyName Tan
96 schema:givenName C. J. Kenneth
97 rdf:type schema:Person
98 Ne7604879a61043fc81f334ebbb569c90 rdf:first N6c953ed31b65414c9b8df27fc410dd26
99 rdf:rest N1ba34eb22e9549509922b55f47db0549
100 Nfee1c6233f464c4e89cf96fd949a9bf1 rdf:first sg:person.01347725471.75
101 rdf:rest N98693c32155e4945a2547f6b9aa5796c
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.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
109 schema:familyName Tang
110 schema:givenName Chuan Yi
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
112 rdf:type schema:Person
113 sg:person.01347725471.75 schema:affiliation https://www.grid.ac/institutes/grid.412111.6
114 schema:familyName Chen
115 schema:givenName Yen Hung
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01347725471.75
117 rdf:type schema:Person
118 sg:pub.10.1007/bf01955679 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038787545
119 https://doi.org/10.1007/bf01955679
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bf02459635 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007125460
122 https://doi.org/10.1007/bf02459635
123 rdf:type schema:CreativeWork
124 sg:pub.10.1023/a:1009885610075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044701682
125 https://doi.org/10.1023/a:1009885610075
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1006/jagm.1997.0882 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038662866
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/b978-0-444-88071-0.50010-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007810942
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/s0166-218x(98)00079-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034216725
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1016/s0304-3975(97)00240-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047421142
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1016/s0304-3975(99)00324-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030133750
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1017/cbo9780511574931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098674485
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1089/cmb.1994.1.337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059245085
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1137/0128004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839274
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1137/s0097539796313507 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880147
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1145/321796.321811 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049170127
146 rdf:type schema:CreativeWork
147 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
148 schema:name Department of Computer Science, National Tsing Hua University, 300, Hsinchu, Taiwan, R.O.C.
149 rdf:type schema:Organization
150 https://www.grid.ac/institutes/grid.412111.6 schema:alternateName National University of Kaohsiung
151 schema:name Department of Applied Mathematics, National University of Kaohsiung, 811, Kaohsiung, Taiwan, R.O.C.
152 rdf:type schema:Organization
 




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


...