A Space Efficient Algorithm for Sequence Alignment with Inversions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003-06-24

AUTHORS

Yong Gao , Junfeng Wu , Robert Niewiadomski , Yang Wang , Zhi-Zhong Chen , Guohui Lin

ABSTRACT

A dynamic programming algorithm to find an optimal alignment for a pair of DNA sequences has been described by Schöniger and Waterman. The alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. With the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in O(n2m2) time and consumes O(n2m2) space, where n and m are the lengths of the input sequences respectively. We develop a space efficient algorithm to compute such an optimal alignment which consumes only O(nm) space within the same amount of time. Our algorithm enables the computation for a pair of DNA sequences of length up to 10,000 to be carried out on an ordinary desktop computer. Simulation study is conducted to verify some biological facts about gene shuffling across species. More... »

PAGES

57-67

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45071-8_8

DOI

http://dx.doi.org/10.1007/3-540-45071-8_8

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0604", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Genetics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gao", 
        "givenName": "Yong", 
        "id": "sg:person.014605202764.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014605202764.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Junfeng", 
        "id": "sg:person.015402563364.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402563364.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Niewiadomski", 
        "givenName": "Robert", 
        "id": "sg:person.015135200643.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015135200643.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Yang", 
        "id": "sg:person.016621652565.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621652565.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Mathematical Sciences, Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Mathematical Sciences, Tokyo Denki Univ., 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": "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Guohui", 
        "id": "sg:person.01130357621.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-06-24", 
    "datePublishedReg": "2003-06-24", 
    "description": "A dynamic programming algorithm to find an optimal alignment for a pair of DNA sequences has been described by Sch\u00f6niger and Waterman. The alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. With the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in O(n2m2) time and consumes O(n2m2) space, where n and m are the lengths of the input sequences respectively. We develop a space efficient algorithm to compute such an optimal alignment which consumes only O(nm) space within the same amount of time. Our algorithm enables the computation for a pair of DNA sequences of length up to 10,000 to be carried out on an ordinary desktop computer. Simulation study is conducted to verify some biological facts about gene shuffling across species.", 
    "editor": [
      {
        "familyName": "Warnow", 
        "givenName": "Tandy", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45071-8_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40534-4", 
        "978-3-540-45071-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "DNA sequences", 
      "space-efficient algorithms", 
      "efficient algorithm", 
      "optimal alignment", 
      "sequence alignment", 
      "single nucleotide", 
      "ordinary desktop computer", 
      "dynamic programming algorithm", 
      "desktop computer", 
      "algorithm runs", 
      "sequence", 
      "programming algorithm", 
      "only substitution", 
      "reversed complement", 
      "input sequence", 
      "algorithm", 
      "biological facts", 
      "genes", 
      "nucleotides", 
      "species", 
      "deletion", 
      "computer", 
      "alignment", 
      "substrings", 
      "computation", 
      "simulation study", 
      "pairs", 
      "substitution", 
      "space", 
      "insertion", 
      "complement", 
      "length", 
      "pairwise", 
      "time", 
      "same amount", 
      "inversion", 
      "amount", 
      "Waterman", 
      "run", 
      "study", 
      "restriction", 
      "fact", 
      "Sch\u00f6niger"
    ], 
    "name": "A Space Efficient Algorithm for Sequence Alignment with Inversions", 
    "pagination": "57-67", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043429379"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45071-8_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45071-8_8", 
      "https://app.dimensions.ai/details/publication/pub.1043429379"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "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_398.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45071-8_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/3-540-45071-8_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/3-540-45071-8_8'

Turtle is a human-readable linked data format.

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

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-45071-8_8'


 

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

146 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45071-8_8 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author N38051ec6375747a3a3965b3f66d3f40c
4 schema:datePublished 2003-06-24
5 schema:datePublishedReg 2003-06-24
6 schema:description A dynamic programming algorithm to find an optimal alignment for a pair of DNA sequences has been described by Schöniger and Waterman. The alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. With the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in O(n2m2) time and consumes O(n2m2) space, where n and m are the lengths of the input sequences respectively. We develop a space efficient algorithm to compute such an optimal alignment which consumes only O(nm) space within the same amount of time. Our algorithm enables the computation for a pair of DNA sequences of length up to 10,000 to be carried out on an ordinary desktop computer. Simulation study is conducted to verify some biological facts about gene shuffling across species.
7 schema:editor Nd67393e97abc453e8e5f01cfff09fbf7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2a684dcd51af4822a44def03976229fd
12 schema:keywords DNA sequences
13 Schöniger
14 Waterman
15 algorithm
16 algorithm runs
17 alignment
18 amount
19 biological facts
20 complement
21 computation
22 computer
23 deletion
24 desktop computer
25 dynamic programming algorithm
26 efficient algorithm
27 fact
28 genes
29 input sequence
30 insertion
31 inversion
32 length
33 nucleotides
34 only substitution
35 optimal alignment
36 ordinary desktop computer
37 pairs
38 pairwise
39 programming algorithm
40 restriction
41 reversed complement
42 run
43 same amount
44 sequence
45 sequence alignment
46 simulation study
47 single nucleotide
48 space
49 space-efficient algorithms
50 species
51 study
52 substitution
53 substrings
54 time
55 schema:name A Space Efficient Algorithm for Sequence Alignment with Inversions
56 schema:pagination 57-67
57 schema:productId N3f37d52d4dd74f26879b437a3ceb74bc
58 N75c6da7aaa6e4833b04d7eff514e9c6d
59 schema:publisher N300e373e55294136b2f4080ec38305ee
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043429379
61 https://doi.org/10.1007/3-540-45071-8_8
62 schema:sdDatePublished 2022-05-20T07:47
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher Ne0b62cb9a52f4c60b94b6da98b1097c8
65 schema:url https://doi.org/10.1007/3-540-45071-8_8
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N28e827dac16b42fe88dbf27450ce038d rdf:first sg:person.015654265661.98
70 rdf:rest N3755ad0d8f4746cdb736b0c92ab4d6e9
71 N2a684dcd51af4822a44def03976229fd schema:isbn 978-3-540-40534-4
72 978-3-540-45071-9
73 schema:name Computing and Combinatorics
74 rdf:type schema:Book
75 N300e373e55294136b2f4080ec38305ee schema:name Springer Nature
76 rdf:type schema:Organisation
77 N3755ad0d8f4746cdb736b0c92ab4d6e9 rdf:first sg:person.01130357621.02
78 rdf:rest rdf:nil
79 N38051ec6375747a3a3965b3f66d3f40c rdf:first sg:person.014605202764.33
80 rdf:rest Nfebdc8a4ea4041e18af51ba25a325b62
81 N3f37d52d4dd74f26879b437a3ceb74bc schema:name doi
82 schema:value 10.1007/3-540-45071-8_8
83 rdf:type schema:PropertyValue
84 N42a8b9ffcddf48b491eebab4d8be8b93 rdf:first sg:person.015135200643.40
85 rdf:rest N4385458b08c74aba87557590c0dd127c
86 N4385458b08c74aba87557590c0dd127c rdf:first sg:person.016621652565.27
87 rdf:rest N28e827dac16b42fe88dbf27450ce038d
88 N75c6da7aaa6e4833b04d7eff514e9c6d schema:name dimensions_id
89 schema:value pub.1043429379
90 rdf:type schema:PropertyValue
91 Na2a576961ddc44eaa2b556cea9b43659 schema:familyName Zhu
92 schema:givenName Binhai
93 rdf:type schema:Person
94 Nbae7afba57bb48a2be8f94b7546af2e4 schema:familyName Warnow
95 schema:givenName Tandy
96 rdf:type schema:Person
97 Ncee78eb470fa4bca817f6c99a512d3fb rdf:first Na2a576961ddc44eaa2b556cea9b43659
98 rdf:rest rdf:nil
99 Nd67393e97abc453e8e5f01cfff09fbf7 rdf:first Nbae7afba57bb48a2be8f94b7546af2e4
100 rdf:rest Ncee78eb470fa4bca817f6c99a512d3fb
101 Ne0b62cb9a52f4c60b94b6da98b1097c8 schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 Nfebdc8a4ea4041e18af51ba25a325b62 rdf:first sg:person.015402563364.24
104 rdf:rest N42a8b9ffcddf48b491eebab4d8be8b93
105 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
106 schema:name Biological Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
109 schema:name Genetics
110 rdf:type schema:DefinedTerm
111 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
112 schema:familyName Lin
113 schema:givenName Guohui
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
115 rdf:type schema:Person
116 sg:person.014605202764.33 schema:affiliation grid-institutes:grid.17089.37
117 schema:familyName Gao
118 schema:givenName Yong
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014605202764.33
120 rdf:type schema:Person
121 sg:person.015135200643.40 schema:affiliation grid-institutes:grid.17089.37
122 schema:familyName Niewiadomski
123 schema:givenName Robert
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015135200643.40
125 rdf:type schema:Person
126 sg:person.015402563364.24 schema:affiliation grid-institutes:grid.17089.37
127 schema:familyName Wu
128 schema:givenName Junfeng
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402563364.24
130 rdf:type schema:Person
131 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
132 schema:familyName Chen
133 schema:givenName Zhi-Zhong
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
135 rdf:type schema:Person
136 sg:person.016621652565.27 schema:affiliation grid-institutes:grid.17089.37
137 schema:familyName Wang
138 schema:givenName Yang
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621652565.27
140 rdf:type schema:Person
141 grid-institutes:grid.17089.37 schema:alternateName Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
142 schema:name Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada
143 rdf:type schema:Organization
144 grid-institutes:grid.412773.4 schema:alternateName Mathematical Sciences, Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
145 schema:name Mathematical Sciences, Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
146 rdf:type schema:Organization
 




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


...