Computing a Consensus Phylogeny via Leaf Removal View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019-05-09

AUTHORS

Zhi-Zhong Chen , Shohei Ueta , Jingyu Li , Lusheng Wang

ABSTRACT

Given a set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{T} = \{T_1, T_2, \ldots , T_m\}$$\end{document} of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [6] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems, but it seems that their algorithm for the parameterized version of AST-LR is flawed [7]. In this paper, we present a new algorithm for the parameterized version of AST-LR and also show that Chauve et al.’s algorithm for the parameterized version of AST-LR-d can be sped up by an exponential factor. We further design heuristic integer-linear programming (ILP for short) models for AST-LR and AST-LR-d. Our experimental results show that the heuristic models can be used to significantly speed up solving the exact models proposed in [7]. More... »

PAGES

3-15

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-20242-2_1

DOI

http://dx.doi.org/10.1007/978-3-030-20242-2_1

DIMENSIONS

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


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/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": "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ueta", 
        "givenName": "Shohei", 
        "id": "sg:person.011331715107.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011331715107.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Jingyu", 
        "id": "sg:person.012435754010.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012435754010.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2019-05-09", 
    "datePublishedReg": "2019-05-09", 
    "description": "Given a set \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal{T} = \\{T_1, T_2, \\ldots , T_m\\}$$\\end{document} of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [6] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems, but it seems that their algorithm for the parameterized version of AST-LR is flawed\u00a0[7]. In this paper, we present a new algorithm for the parameterized version of AST-LR and also show that Chauve et al.\u2019s algorithm for the parameterized version of AST-LR-d can be sped up by an exponential factor. We further design heuristic integer-linear programming (ILP for short) models for AST-LR and AST-LR-d. Our experimental results show that the heuristic models can be used to significantly speed up solving the exact models proposed in [7].", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Zhipeng", 
        "type": "Person"
      }, 
      {
        "familyName": "Skums", 
        "givenName": "Pavel", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Min", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-20242-2_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-20241-5", 
        "978-3-030-20242-2"
      ], 
      "name": "Bioinformatics Research and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "consensus phylogeny", 
      "phylogenetic tree", 
      "leaves", 
      "leaf removal", 
      "trees", 
      "input trees", 
      "phylogeny", 
      "total number", 
      "maximum number", 
      "number", 
      "factors", 
      "tree T", 
      "chauve", 
      "removal", 
      "first objective", 
      "model", 
      "set", 
      "results", 
      "heuristic model", 
      "objective", 
      "version", 
      "al", 
      "NPs", 
      "problem", 
      "new algorithm", 
      "algorithm", 
      "set X", 
      "integer linear programming model", 
      "exact model", 
      "exponential factor", 
      "programming model", 
      "paper", 
      "experimental results"
    ], 
    "name": "Computing a Consensus Phylogeny via Leaf Removal", 
    "pagination": "3-15", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1115013345"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-20242-2_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-20242-2_1", 
      "https://app.dimensions.ai/details/publication/pub.1115013345"
    ], 
    "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_245.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-20242-2_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/978-3-030-20242-2_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/978-3-030-20242-2_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-20242-2_1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-20242-2_1'


 

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

127 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-20242-2_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne845c3cb5ac840348ad8ac3c963067e1
4 schema:datePublished 2019-05-09
5 schema:datePublishedReg 2019-05-09
6 schema:description Given a set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{T} = \{T_1, T_2, \ldots , T_m\}$$\end{document} of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [6] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems, but it seems that their algorithm for the parameterized version of AST-LR is flawed [7]. In this paper, we present a new algorithm for the parameterized version of AST-LR and also show that Chauve et al.’s algorithm for the parameterized version of AST-LR-d can be sped up by an exponential factor. We further design heuristic integer-linear programming (ILP for short) models for AST-LR and AST-LR-d. Our experimental results show that the heuristic models can be used to significantly speed up solving the exact models proposed in [7].
7 schema:editor Nc4cb547603c64a96b9009a669dda2991
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2fae740393a340ce8bb61949e6ba0198
12 schema:keywords NPs
13 al
14 algorithm
15 chauve
16 consensus phylogeny
17 exact model
18 experimental results
19 exponential factor
20 factors
21 first objective
22 heuristic model
23 input trees
24 integer linear programming model
25 leaf removal
26 leaves
27 maximum number
28 model
29 new algorithm
30 number
31 objective
32 paper
33 phylogenetic tree
34 phylogeny
35 problem
36 programming model
37 removal
38 results
39 set
40 set X
41 total number
42 tree T
43 trees
44 version
45 schema:name Computing a Consensus Phylogeny via Leaf Removal
46 schema:pagination 3-15
47 schema:productId N685c751757ef48db8b52efabded4fb92
48 Nc3519ef03024457dba6b1237a92966c5
49 schema:publisher N8d15e038ba0d4aeab6d7fbd38be7d5cf
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1115013345
51 https://doi.org/10.1007/978-3-030-20242-2_1
52 schema:sdDatePublished 2022-05-20T07:44
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher Nf9271862bbed42ef8f90f940e790b902
55 schema:url https://doi.org/10.1007/978-3-030-20242-2_1
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N2fae740393a340ce8bb61949e6ba0198 schema:isbn 978-3-030-20241-5
60 978-3-030-20242-2
61 schema:name Bioinformatics Research and Applications
62 rdf:type schema:Book
63 N3156a26641bf4a98ab1d710503bb10fd schema:familyName Skums
64 schema:givenName Pavel
65 rdf:type schema:Person
66 N52d3d05667864ea1a3969b863c75186c schema:familyName Li
67 schema:givenName Min
68 rdf:type schema:Person
69 N685c751757ef48db8b52efabded4fb92 schema:name doi
70 schema:value 10.1007/978-3-030-20242-2_1
71 rdf:type schema:PropertyValue
72 N7ae16fc9dae6418d92429726a55851e6 rdf:first sg:person.011331715107.51
73 rdf:rest N8b3cc41e3bbd4159be08f2c28f228b5b
74 N8b3cc41e3bbd4159be08f2c28f228b5b rdf:first sg:person.012435754010.54
75 rdf:rest Nee484c0d1bc74514a8e72cde208ec37e
76 N8d15e038ba0d4aeab6d7fbd38be7d5cf schema:name Springer Nature
77 rdf:type schema:Organisation
78 Nc3519ef03024457dba6b1237a92966c5 schema:name dimensions_id
79 schema:value pub.1115013345
80 rdf:type schema:PropertyValue
81 Nc4cb547603c64a96b9009a669dda2991 rdf:first Nf4fb6368ac24492eb1adc013aae351a0
82 rdf:rest Ne3f9cba0726643bf8fe4b05aaa6dd4e2
83 Nced5e8ffda924dd690d089c41b73ac52 rdf:first N52d3d05667864ea1a3969b863c75186c
84 rdf:rest rdf:nil
85 Ne3f9cba0726643bf8fe4b05aaa6dd4e2 rdf:first N3156a26641bf4a98ab1d710503bb10fd
86 rdf:rest Nced5e8ffda924dd690d089c41b73ac52
87 Ne845c3cb5ac840348ad8ac3c963067e1 rdf:first sg:person.015654265661.98
88 rdf:rest N7ae16fc9dae6418d92429726a55851e6
89 Nee484c0d1bc74514a8e72cde208ec37e rdf:first sg:person.01105113721.52
90 rdf:rest rdf:nil
91 Nf4fb6368ac24492eb1adc013aae351a0 schema:familyName Cai
92 schema:givenName Zhipeng
93 rdf:type schema:Person
94 Nf9271862bbed42ef8f90f940e790b902 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.01105113721.52 schema:affiliation grid-institutes:None
103 schema:familyName Wang
104 schema:givenName Lusheng
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
106 rdf:type schema:Person
107 sg:person.011331715107.51 schema:affiliation grid-institutes:grid.412773.4
108 schema:familyName Ueta
109 schema:givenName Shohei
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011331715107.51
111 rdf:type schema:Person
112 sg:person.012435754010.54 schema:affiliation grid-institutes:None
113 schema:familyName Li
114 schema:givenName Jingyu
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012435754010.54
116 rdf:type schema:Person
117 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
118 schema:familyName Chen
119 schema:givenName Zhi-Zhong
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
121 rdf:type schema:Person
122 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
123 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
124 rdf:type schema:Organization
125 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
126 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
127 rdf:type schema:Organization
 




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


...