Alignment between Two Multiple Alignments View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Bin Ma , Zhuozhi Wang , Kaizhong Zhang

ABSTRACT

Alignment of two multiple alignments arises naturally when constructing approximate multiple sequence alignments progressively. In this paper, we consider the problem of alignment of two multiple alignments with SP-score and linear gap costs. When there is no gap opening cost, this problem can be solved using the well-known dynamic programming algorithm for two sequences by viewing each column in the multiple alignments as an element. However if there are gap opening costs (sometimes referred as affine gap costs) then the problem becomes non-trivial. Gotoh [4] suggested a procedure for this problem and stated that “the total arithmetic operations used is close to (quadratic) in typical cases”. Kececioglu and Zhang [7] gave heuristic algorithms based on optimistic and pessimistic gap counts and conjectured that this problem is NP-complete. In this paper we prove that this problem is indeed NP-complete and therefore settle this open problem. We then propose another heuristic algorithm for this problem. More... »

PAGES

254-265

References to SciGraph publications

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-540-40311-1
978-3-540-44888-4

Author Affiliations

From Grant

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44888-8_19

DOI

http://dx.doi.org/10.1007/3-540-44888-8_19

DIMENSIONS

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


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": "Western University", 
          "id": "https://www.grid.ac/institutes/grid.39381.30", 
          "name": [
            "Dept. of Computer Science, University of Western Ontario, London, Ont., N6A 5B7, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ma", 
        "givenName": "Bin", 
        "id": "sg:person.01221430663.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Western University", 
          "id": "https://www.grid.ac/institutes/grid.39381.30", 
          "name": [
            "Dept. of Computer Science, University of Western Ontario, London, Ont., N6A 5B7, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Zhuozhi", 
        "id": "sg:person.0733714437.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0733714437.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Western University", 
          "id": "https://www.grid.ac/institutes/grid.39381.30", 
          "name": [
            "Dept. of Computer Science, University of Western Ontario, London, Ont., N6A 5B7, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Kaizhong", 
        "id": "sg:person.015001674137.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015001674137.24"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0022-2836(70)90057-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021169618"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-2836(82)90398-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025042064"
        ], 
        "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": "sg:pub.10.1007/bfb0030790", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035409083", 
          "https://doi.org/10.1007/bfb0030790"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/106652701753307511", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059204911"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/cmb.1994.1.337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059245085"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "Alignment of two multiple alignments arises naturally when constructing approximate multiple sequence alignments progressively. In this paper, we consider the problem of alignment of two multiple alignments with SP-score and linear gap costs. When there is no gap opening cost, this problem can be solved using the well-known dynamic programming algorithm for two sequences by viewing each column in the multiple alignments as an element. However if there are gap opening costs (sometimes referred as affine gap costs) then the problem becomes non-trivial. Gotoh [4] suggested a procedure for this problem and stated that \u201cthe total arithmetic operations used is close to (quadratic) in typical cases\u201d. Kececioglu and Zhang [7] gave heuristic algorithms based on optimistic and pessimistic gap counts and conjectured that this problem is NP-complete. In this paper we prove that this problem is indeed NP-complete and therefore settle this open problem. We then propose another heuristic algorithm for this problem.", 
    "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_19", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.2909762", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-40311-1", 
        "978-3-540-44888-4"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "name": "Alignment between Two Multiple Alignments", 
    "pagination": "254-265", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44888-8_19"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "35f35614980be333358f3f7f87e21b5b80daf5f09a5df6d222938b186d4aa601"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011323716"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44888-8_19", 
      "https://app.dimensions.ai/details/publication/pub.1011323716"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T17:12", 
    "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_8678_00000250.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44888-8_19"
  }
]
 

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_19'

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_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44888-8_19'

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_19'


 

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

113 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44888-8_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfadc5a056d9349e7b6820a41aa8b3a8d
4 schema:citation sg:pub.10.1007/bfb0030790
5 https://doi.org/10.1016/0022-0000(91)90023-x
6 https://doi.org/10.1016/0022-2836(70)90057-4
7 https://doi.org/10.1016/0022-2836(82)90398-9
8 https://doi.org/10.1016/s0304-3975(99)00324-2
9 https://doi.org/10.1089/106652701753307511
10 https://doi.org/10.1089/cmb.1994.1.337
11 schema:datePublished 2003
12 schema:datePublishedReg 2003-01-01
13 schema:description Alignment of two multiple alignments arises naturally when constructing approximate multiple sequence alignments progressively. In this paper, we consider the problem of alignment of two multiple alignments with SP-score and linear gap costs. When there is no gap opening cost, this problem can be solved using the well-known dynamic programming algorithm for two sequences by viewing each column in the multiple alignments as an element. However if there are gap opening costs (sometimes referred as affine gap costs) then the problem becomes non-trivial. Gotoh [4] suggested a procedure for this problem and stated that “the total arithmetic operations used is close to (quadratic) in typical cases”. Kececioglu and Zhang [7] gave heuristic algorithms based on optimistic and pessimistic gap counts and conjectured that this problem is NP-complete. In this paper we prove that this problem is indeed NP-complete and therefore settle this open problem. We then propose another heuristic algorithm for this problem.
14 schema:editor N0be64f8b4cf049b9b855bfc2a6a8ad14
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N72bbbc0b0c51475b9e6e79cc788df84f
19 schema:name Alignment between Two Multiple Alignments
20 schema:pagination 254-265
21 schema:productId N3e1b5691f8c041bd9b4b6175d58f0796
22 Ne5734205bfae49e2aca97721d39bb5e3
23 Nf3123d498a634132aefd4470f7531aaa
24 schema:publisher Ndf4e0d114c6543dea61e623d3c0d8701
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011323716
26 https://doi.org/10.1007/3-540-44888-8_19
27 schema:sdDatePublished 2019-04-15T17:12
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N956e5a8c959545e591adb36177f3d040
30 schema:url http://link.springer.com/10.1007/3-540-44888-8_19
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N0be64f8b4cf049b9b855bfc2a6a8ad14 rdf:first N9e119c45d1eb431990eb45ce1c71f514
35 rdf:rest N7c007e2649c04798adab958da42cd836
36 N3e1b5691f8c041bd9b4b6175d58f0796 schema:name readcube_id
37 schema:value 35f35614980be333358f3f7f87e21b5b80daf5f09a5df6d222938b186d4aa601
38 rdf:type schema:PropertyValue
39 N6e2000bb0ad54edbaaa606dd5048efab schema:familyName Crochemore
40 schema:givenName Maxime
41 rdf:type schema:Person
42 N72bbbc0b0c51475b9e6e79cc788df84f schema:isbn 978-3-540-40311-1
43 978-3-540-44888-4
44 schema:name Combinatorial Pattern Matching
45 rdf:type schema:Book
46 N7c007e2649c04798adab958da42cd836 rdf:first Nd937849f747641f29c2fc0852ba31706
47 rdf:rest Nd8cf69b05d574899b3ee2dec2f9a9d55
48 N956e5a8c959545e591adb36177f3d040 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N9e119c45d1eb431990eb45ce1c71f514 schema:familyName Baeza-Yates
51 schema:givenName Ricardo
52 rdf:type schema:Person
53 Nc564b443dc5746a893ff01899c53c8ce rdf:first sg:person.0733714437.23
54 rdf:rest Ndf3e3e23e1be418bba35c9eb48e2be84
55 Nd8cf69b05d574899b3ee2dec2f9a9d55 rdf:first N6e2000bb0ad54edbaaa606dd5048efab
56 rdf:rest rdf:nil
57 Nd937849f747641f29c2fc0852ba31706 schema:familyName Chávez
58 schema:givenName Edgar
59 rdf:type schema:Person
60 Ndf3e3e23e1be418bba35c9eb48e2be84 rdf:first sg:person.015001674137.24
61 rdf:rest rdf:nil
62 Ndf4e0d114c6543dea61e623d3c0d8701 schema:location Berlin, Heidelberg
63 schema:name Springer Berlin Heidelberg
64 rdf:type schema:Organisation
65 Ne5734205bfae49e2aca97721d39bb5e3 schema:name doi
66 schema:value 10.1007/3-540-44888-8_19
67 rdf:type schema:PropertyValue
68 Nf3123d498a634132aefd4470f7531aaa schema:name dimensions_id
69 schema:value pub.1011323716
70 rdf:type schema:PropertyValue
71 Nfadc5a056d9349e7b6820a41aa8b3a8d rdf:first sg:person.01221430663.16
72 rdf:rest Nc564b443dc5746a893ff01899c53c8ce
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
77 schema:name Computation Theory and Mathematics
78 rdf:type schema:DefinedTerm
79 sg:grant.2909762 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-44888-8_19
80 rdf:type schema:MonetaryGrant
81 sg:person.01221430663.16 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
82 schema:familyName Ma
83 schema:givenName Bin
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221430663.16
85 rdf:type schema:Person
86 sg:person.015001674137.24 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
87 schema:familyName Zhang
88 schema:givenName Kaizhong
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015001674137.24
90 rdf:type schema:Person
91 sg:person.0733714437.23 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
92 schema:familyName Wang
93 schema:givenName Zhuozhi
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0733714437.23
95 rdf:type schema:Person
96 sg:pub.10.1007/bfb0030790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035409083
97 https://doi.org/10.1007/bfb0030790
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0022-2836(70)90057-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021169618
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0022-2836(82)90398-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025042064
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/s0304-3975(99)00324-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030133750
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1089/106652701753307511 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059204911
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1089/cmb.1994.1.337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059245085
110 rdf:type schema:CreativeWork
111 https://www.grid.ac/institutes/grid.39381.30 schema:alternateName Western University
112 schema:name Dept. of Computer Science, University of Western Ontario, London, Ont., N6A 5B7, Canada
113 rdf:type schema:Organization
 




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


...