Chaining Algorithms for Alignment of Draft Sequence View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Mukund Sundararajan , Michael Brudno , Kerrin Small , Arend Sidow , Serafim Batzoglou

ABSTRACT

In this paper we propose a chaining method that can align a draft genomic sequence against a finished genome. We introduce the use of an overlap tree to enhance the state information available to the chaining procedure in the context of sparse dynamic programming, and demonstrate that the resulting procedure more accurately penalizes the various biological rearrangements. The algorithm is tested on a whole genome alignment of seven yeast species. We also demonstrate a variation on the algorithm that can be used for co-assembly of two genomes and show how it can improve the current assembly of the Ciona savignyi (sea squirt) genome. More... »

PAGES

326-337

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_28

DOI

http://dx.doi.org/10.1007/978-3-540-30219-3_28

DIMENSIONS

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


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": "Department of Computer Science, Stanford University, 94305, Stanford, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Computer Science, Stanford University, 94305, Stanford, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sundararajan", 
        "givenName": "Mukund", 
        "id": "sg:person.010222560615.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010222560615.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Stanford University, 94305, Stanford, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Computer Science, Stanford University, 94305, Stanford, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brudno", 
        "givenName": "Michael", 
        "id": "sg:person.01253563237.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01253563237.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Genetics, Stanford University, 94305, Stanford, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Genetics, Stanford University, 94305, Stanford, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Small", 
        "givenName": "Kerrin", 
        "id": "sg:person.01212126575.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212126575.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Pathology, Stanford University, 94305, Stanford, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Genetics, Stanford University, 94305, Stanford, California, USA", 
            "Department of Pathology, Stanford University, 94305, Stanford, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sidow", 
        "givenName": "Arend", 
        "id": "sg:person.0771606520.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0771606520.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Stanford University, 94305, Stanford, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Department of Computer Science, Stanford University, 94305, Stanford, California, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Batzoglou", 
        "givenName": "Serafim", 
        "id": "sg:person.0606462727.66", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0606462727.66"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In this paper we propose a chaining method that can align a draft genomic sequence against a finished genome. We introduce the use of an overlap tree to enhance the state information available to the chaining procedure in the context of sparse dynamic programming, and demonstrate that the resulting procedure more accurately penalizes the various biological rearrangements. The algorithm is tested on a whole genome alignment of seven yeast species. We also demonstrate a variation on the algorithm that can be used for co-assembly of two genomes and show how it can improve the current assembly of the Ciona savignyi (sea squirt) genome.", 
    "editor": [
      {
        "familyName": "Jonassen", 
        "givenName": "Inge", 
        "type": "Person"
      }, 
      {
        "familyName": "Kim", 
        "givenName": "Junhyong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30219-3_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-23018-2", 
        "978-3-540-30219-3"
      ], 
      "name": "Algorithms in Bioinformatics", 
      "type": "Book"
    }, 
    "keywords": [
      "draft genomic sequence", 
      "whole genome alignments", 
      "draft sequence", 
      "genomic sequences", 
      "current assembly", 
      "finished genomes", 
      "genome alignments", 
      "yeast species", 
      "genome", 
      "biological rearrangements", 
      "sequence", 
      "species", 
      "trees", 
      "assembly", 
      "rearrangement", 
      "sparse dynamic programming", 
      "alignment", 
      "variation", 
      "information", 
      "context", 
      "use", 
      "method", 
      "procedure", 
      "programming", 
      "algorithm", 
      "dynamic programming", 
      "paper", 
      "state information", 
      "overlap tree", 
      "Ciona savignyi (sea squirt) genome", 
      "savignyi (sea squirt) genome"
    ], 
    "name": "Chaining Algorithms for Alignment of Draft Sequence", 
    "pagination": "326-337", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039123727"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30219-3_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30219-3_28", 
      "https://app.dimensions.ai/details/publication/pub.1039123727"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_310.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30219-3_28"
  }
]
 

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-540-30219-3_28'

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-540-30219-3_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30219-3_28'

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-540-30219-3_28'


 

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

128 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30219-3_28 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author Nb06b74854fdb40cf9a42228adae1cf2b
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description In this paper we propose a chaining method that can align a draft genomic sequence against a finished genome. We introduce the use of an overlap tree to enhance the state information available to the chaining procedure in the context of sparse dynamic programming, and demonstrate that the resulting procedure more accurately penalizes the various biological rearrangements. The algorithm is tested on a whole genome alignment of seven yeast species. We also demonstrate a variation on the algorithm that can be used for co-assembly of two genomes and show how it can improve the current assembly of the Ciona savignyi (sea squirt) genome.
7 schema:editor N6912acc59fef494ebe2ae046fb388536
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nff71de8aeb9448238d7394918c238e3f
12 schema:keywords Ciona savignyi (sea squirt) genome
13 algorithm
14 alignment
15 assembly
16 biological rearrangements
17 context
18 current assembly
19 draft genomic sequence
20 draft sequence
21 dynamic programming
22 finished genomes
23 genome
24 genome alignments
25 genomic sequences
26 information
27 method
28 overlap tree
29 paper
30 procedure
31 programming
32 rearrangement
33 savignyi (sea squirt) genome
34 sequence
35 sparse dynamic programming
36 species
37 state information
38 trees
39 use
40 variation
41 whole genome alignments
42 yeast species
43 schema:name Chaining Algorithms for Alignment of Draft Sequence
44 schema:pagination 326-337
45 schema:productId N0743721f8f164a85a13a9914343b7919
46 Nc57c58013cda4fbeb946c622b1f466a4
47 schema:publisher N71593c2bd3254369b5f767527b397cd6
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039123727
49 https://doi.org/10.1007/978-3-540-30219-3_28
50 schema:sdDatePublished 2021-11-01T18:55
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher Ncb20e481b53749f493c2833b831e167c
53 schema:url https://doi.org/10.1007/978-3-540-30219-3_28
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N00757afe99ed41098d37ae145ea8d9cc rdf:first sg:person.01253563237.25
58 rdf:rest N4871f1cd9578420ba1fb737f1c5928a7
59 N0743721f8f164a85a13a9914343b7919 schema:name dimensions_id
60 schema:value pub.1039123727
61 rdf:type schema:PropertyValue
62 N1a2c394e794d4ee7b762651879b43b22 rdf:first sg:person.0606462727.66
63 rdf:rest rdf:nil
64 N4871f1cd9578420ba1fb737f1c5928a7 rdf:first sg:person.01212126575.59
65 rdf:rest Na93193f4af454ae486954c55149dd7ee
66 N67dfa85a27f6420485acdfdb54aaaf19 rdf:first Na27eeb4b469f42ccb9178eed12e73406
67 rdf:rest rdf:nil
68 N6912acc59fef494ebe2ae046fb388536 rdf:first Nf0c3fd0051c64259a8b2853d1a169e86
69 rdf:rest N67dfa85a27f6420485acdfdb54aaaf19
70 N71593c2bd3254369b5f767527b397cd6 schema:name Springer Nature
71 rdf:type schema:Organisation
72 Na27eeb4b469f42ccb9178eed12e73406 schema:familyName Kim
73 schema:givenName Junhyong
74 rdf:type schema:Person
75 Na93193f4af454ae486954c55149dd7ee rdf:first sg:person.0771606520.69
76 rdf:rest N1a2c394e794d4ee7b762651879b43b22
77 Nb06b74854fdb40cf9a42228adae1cf2b rdf:first sg:person.010222560615.03
78 rdf:rest N00757afe99ed41098d37ae145ea8d9cc
79 Nc57c58013cda4fbeb946c622b1f466a4 schema:name doi
80 schema:value 10.1007/978-3-540-30219-3_28
81 rdf:type schema:PropertyValue
82 Ncb20e481b53749f493c2833b831e167c schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Nf0c3fd0051c64259a8b2853d1a169e86 schema:familyName Jonassen
85 schema:givenName Inge
86 rdf:type schema:Person
87 Nff71de8aeb9448238d7394918c238e3f schema:isbn 978-3-540-23018-2
88 978-3-540-30219-3
89 schema:name Algorithms in Bioinformatics
90 rdf:type schema:Book
91 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
92 schema:name Biological Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
95 schema:name Genetics
96 rdf:type schema:DefinedTerm
97 sg:person.010222560615.03 schema:affiliation grid-institutes:grid.168010.e
98 schema:familyName Sundararajan
99 schema:givenName Mukund
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010222560615.03
101 rdf:type schema:Person
102 sg:person.01212126575.59 schema:affiliation grid-institutes:grid.168010.e
103 schema:familyName Small
104 schema:givenName Kerrin
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01212126575.59
106 rdf:type schema:Person
107 sg:person.01253563237.25 schema:affiliation grid-institutes:grid.168010.e
108 schema:familyName Brudno
109 schema:givenName Michael
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01253563237.25
111 rdf:type schema:Person
112 sg:person.0606462727.66 schema:affiliation grid-institutes:grid.168010.e
113 schema:familyName Batzoglou
114 schema:givenName Serafim
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0606462727.66
116 rdf:type schema:Person
117 sg:person.0771606520.69 schema:affiliation grid-institutes:grid.168010.e
118 schema:familyName Sidow
119 schema:givenName Arend
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0771606520.69
121 rdf:type schema:Person
122 grid-institutes:grid.168010.e schema:alternateName Department of Computer Science, Stanford University, 94305, Stanford, California, USA
123 Department of Genetics, Stanford University, 94305, Stanford, California, USA
124 Department of Pathology, Stanford University, 94305, Stanford, California, USA
125 schema:name Department of Computer Science, Stanford University, 94305, Stanford, California, USA
126 Department of Genetics, Stanford University, 94305, Stanford, California, USA
127 Department of Pathology, Stanford University, 94305, Stanford, California, USA
128 rdf:type schema:Organization
 




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


...