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 N6d94f83fb33646a8ab7b6a487f96416e
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 N45f36e96cae944f587b5ae2fa9fea47b
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf N3d2dbe7e84914b3f8ec67d2039735412
25 schema:name The Bottleneck Tree Alignment Problems
26 schema:pagination 631-637
27 schema:productId N1d7efb9d817d47edacaa713f5715f2f5
28 N7fe308c63aaf4a96a5f1f5400694e554
29 Ncd181d995baf44b4aae625f977b1807b
30 schema:publisher N0ead5136943e49f29491230cf17435e7
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 N6787afab940149f4a2695d3902ea0fbc
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 N05fcf41cd5e94006a72a9327441e4cca rdf:first N59070828641847bc9d3085143ef54460
41 rdf:rest Ndb286f79ed3e423fa512238cf5f6bc7e
42 N0a5d2d5ca87542da841c9fe8d11e2585 schema:familyName Tan
43 schema:givenName C. J. Kenneth
44 rdf:type schema:Person
45 N0ead5136943e49f29491230cf17435e7 schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N1d7efb9d817d47edacaa713f5715f2f5 schema:name dimensions_id
49 schema:value pub.1048758676
50 rdf:type schema:PropertyValue
51 N2b243801861940e994dbed12c1afa5b5 schema:familyName Mun
52 schema:givenName Youngsong
53 rdf:type schema:Person
54 N3828a3aa428d4059b983587ba0ff0486 schema:familyName Gervasi
55 schema:givenName Osvaldo
56 rdf:type schema:Person
57 N3d2dbe7e84914b3f8ec67d2039735412 schema:isbn 978-3-540-34075-1
58 978-3-540-34076-8
59 schema:name Computational Science and Its Applications - ICCSA 2006
60 rdf:type schema:Book
61 N3f53fa2697264c5a97811cf66ae4e652 schema:familyName Kumar
62 schema:givenName Vipin
63 rdf:type schema:Person
64 N45f36e96cae944f587b5ae2fa9fea47b rdf:first N512d86db88e14295b5184f0ff40c5a6b
65 rdf:rest N50d3610d977f432b8c6a2967c6bce42a
66 N4f1074b36f594894b3d5fd1789923065 rdf:first sg:person.01312526135.27
67 rdf:rest rdf:nil
68 N50d3610d977f432b8c6a2967c6bce42a rdf:first N3828a3aa428d4059b983587ba0ff0486
69 rdf:rest Na63ce66bcc5b4530b321153331735967
70 N512d86db88e14295b5184f0ff40c5a6b schema:familyName Gavrilova
71 schema:givenName Marina
72 rdf:type schema:Person
73 N59070828641847bc9d3085143ef54460 schema:familyName Lagan√°
74 schema:givenName Antonio
75 rdf:type schema:Person
76 N5fccf190c7e44584b8b232f390f4c4e2 rdf:first Nb4488aa84ec2481fbcd44af2d5fd87c4
77 rdf:rest N05fcf41cd5e94006a72a9327441e4cca
78 N6787afab940149f4a2695d3902ea0fbc schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N6d94f83fb33646a8ab7b6a487f96416e rdf:first sg:person.01347725471.75
81 rdf:rest N4f1074b36f594894b3d5fd1789923065
82 N7fe308c63aaf4a96a5f1f5400694e554 schema:name doi
83 schema:value 10.1007/11751595_67
84 rdf:type schema:PropertyValue
85 N8f75fe9e888b4ac8bb2fbe0059bb574b rdf:first Na8cc988f4f604c149c55a105f330af20
86 rdf:rest rdf:nil
87 Na63ce66bcc5b4530b321153331735967 rdf:first N3f53fa2697264c5a97811cf66ae4e652
88 rdf:rest Naad5c9cdc72547d0952852792b99f7aa
89 Na8cc988f4f604c149c55a105f330af20 schema:familyName Choo
90 schema:givenName Hyunseung
91 rdf:type schema:Person
92 Naad5c9cdc72547d0952852792b99f7aa rdf:first N0a5d2d5ca87542da841c9fe8d11e2585
93 rdf:rest N5fccf190c7e44584b8b232f390f4c4e2
94 Nb4488aa84ec2481fbcd44af2d5fd87c4 schema:familyName Taniar
95 schema:givenName David
96 rdf:type schema:Person
97 Ncd181d995baf44b4aae625f977b1807b schema:name readcube_id
98 schema:value e846e2d2275a8af1668fb9d1dc113bd8dca3dcd00cef8907fcc2241d80304223
99 rdf:type schema:PropertyValue
100 Ndb286f79ed3e423fa512238cf5f6bc7e rdf:first N2b243801861940e994dbed12c1afa5b5
101 rdf:rest N8f75fe9e888b4ac8bb2fbe0059bb574b
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)


...