Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-07-03

AUTHORS

Zhi-Zhong Chen, Lusheng Wang, Zhanyong Wang

ABSTRACT

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. More... »

PAGES

501

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-008-9209-8

DOI

http://dx.doi.org/10.1007/s00453-008-9209-8

DIMENSIONS

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


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": "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, 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": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.35030.35", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Zhanyong", 
        "id": "sg:person.015267027655.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015267027655.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01955679", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038787545", 
          "https://doi.org/10.1007/bf01955679"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008-07-03", 
    "datePublishedReg": "2008-07-03", 
    "description": "Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623\u2013644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494\u2013507, 2002; Tang et al. in J. Comput. Biol. 9:429\u2013446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is\u00a01. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494\u2013507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494\u2013507, 2002) takes O(n11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most\u00a02. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-008-9209-8", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "54"
      }
    ], 
    "keywords": [
      "polynomial time approximation scheme", 
      "polynomial-time approximation algorithm", 
      "approximation algorithm", 
      "first polynomial-time approximation algorithm", 
      "approximation scheme", 
      "computational biology", 
      "et al", 
      "important problem", 
      "algorithm", 
      "scheme", 
      "problem", 
      "cases", 
      "al", 
      "duplication history", 
      "size", 
      "block", 
      "time", 
      "example", 
      "ratio", 
      "region", 
      "biology", 
      "tandem", 
      "duplication blocks", 
      "history", 
      "tandem repeats", 
      "repeats", 
      "paper"
    ], 
    "name": "Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats", 
    "pagination": "501", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053721671"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-008-9209-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-008-9209-8", 
      "https://app.dimensions.ai/details/publication/pub.1053721671"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-20T07:24", 
    "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/article/article_463.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-008-9209-8"
  }
]
 

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/s00453-008-9209-8'

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/s00453-008-9209-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9209-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-008-9209-8'


 

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

106 TRIPLES      22 PREDICATES      53 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-008-9209-8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nbe13f9f7f5784376aa921edbf4198646
4 schema:citation sg:pub.10.1007/bf01955679
5 schema:datePublished 2008-07-03
6 schema:datePublishedReg 2008-07-03
7 schema:description Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3ec899b3f1174dabab6f10eb01b46ea6
12 N4d03790aef984a429f4c2adccbc5ed8d
13 sg:journal.1047644
14 schema:keywords al
15 algorithm
16 approximation algorithm
17 approximation scheme
18 biology
19 block
20 cases
21 computational biology
22 duplication blocks
23 duplication history
24 et al
25 example
26 first polynomial-time approximation algorithm
27 history
28 important problem
29 paper
30 polynomial time approximation scheme
31 polynomial-time approximation algorithm
32 problem
33 ratio
34 region
35 repeats
36 scheme
37 size
38 tandem
39 tandem repeats
40 time
41 schema:name Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats
42 schema:pagination 501
43 schema:productId N7a13b1b474f84a52b36812d4e9f8ff4b
44 Nee3ce0ecd12c4f968c757c7f4260db5d
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053721671
46 https://doi.org/10.1007/s00453-008-9209-8
47 schema:sdDatePublished 2022-05-20T07:24
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N2048ea23dc0940e5962c3c568de4ec6e
50 schema:url https://doi.org/10.1007/s00453-008-9209-8
51 sgo:license sg:explorer/license/
52 sgo:sdDataset articles
53 rdf:type schema:ScholarlyArticle
54 N2048ea23dc0940e5962c3c568de4ec6e schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N3e156eef745a49af9cd49a3e65f78997 rdf:first sg:person.01105113721.52
57 rdf:rest N7bef1a62f3794ba186808f9f8f48b86b
58 N3ec899b3f1174dabab6f10eb01b46ea6 schema:volumeNumber 54
59 rdf:type schema:PublicationVolume
60 N4d03790aef984a429f4c2adccbc5ed8d schema:issueNumber 4
61 rdf:type schema:PublicationIssue
62 N7a13b1b474f84a52b36812d4e9f8ff4b schema:name dimensions_id
63 schema:value pub.1053721671
64 rdf:type schema:PropertyValue
65 N7bef1a62f3794ba186808f9f8f48b86b rdf:first sg:person.015267027655.28
66 rdf:rest rdf:nil
67 Nbe13f9f7f5784376aa921edbf4198646 rdf:first sg:person.015654265661.98
68 rdf:rest N3e156eef745a49af9cd49a3e65f78997
69 Nee3ce0ecd12c4f968c757c7f4260db5d schema:name doi
70 schema:value 10.1007/s00453-008-9209-8
71 rdf:type schema:PropertyValue
72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information and Computing Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
76 schema:name Computation Theory and Mathematics
77 rdf:type schema:DefinedTerm
78 sg:journal.1047644 schema:issn 0178-4617
79 1432-0541
80 schema:name Algorithmica
81 schema:publisher Springer Nature
82 rdf:type schema:Periodical
83 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
84 schema:familyName Wang
85 schema:givenName Lusheng
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
87 rdf:type schema:Person
88 sg:person.015267027655.28 schema:affiliation grid-institutes:grid.35030.35
89 schema:familyName Wang
90 schema:givenName Zhanyong
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015267027655.28
92 rdf:type schema:Person
93 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
94 schema:familyName Chen
95 schema:givenName Zhi-Zhong
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
97 rdf:type schema:Person
98 sg:pub.10.1007/bf01955679 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038787545
99 https://doi.org/10.1007/bf01955679
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
102 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
103 rdf:type schema:Organization
104 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
105 schema:name Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
106 rdf:type schema:Organization
 




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


...