A Linear-Time Algorithm for Studying Genetic Variation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Nikola Stojanovic , Piotr Berman

ABSTRACT

The study of variation in DNA sequences, within the framework of phylogeny or population genetics, for instance, is one of the most important subjects in modern genomics. We here present a new linear-time algorithm for finding maximal k-regions in alignments of three sequences, which can be used for the detection of segments featuring a certain degree of similarity, as well as the boundaries of distinct genomic environments such as gene clusters or haplotype blocks. k-regions are defined as these which have a center sequence whose Hamming distance from any of the alignment rows is at most k, and their determination in the general case is known to be NP-hard. More... »

PAGES

344-354

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11851561_32

DOI

http://dx.doi.org/10.1007/11851561_32

DIMENSIONS

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


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 and Engineering, The University of Texas at Arlington, Arlington, Texas, USA", 
          "id": "http://www.grid.ac/institutes/grid.267315.4", 
          "name": [
            "Department of Computer Science and Engineering, The University of Texas at Arlington, Arlington, Texas, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stojanovic", 
        "givenName": "Nikola", 
        "id": "sg:person.01012555463.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01012555463.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The study of variation in DNA sequences, within the framework of phylogeny or population genetics, for instance, is one of the most important subjects in modern genomics. We here present a new linear-time algorithm for finding maximal k-regions in alignments of three sequences, which can be used for the detection of segments featuring a certain degree of similarity, as well as the boundaries of distinct genomic environments such as gene clusters or haplotype blocks. k-regions are defined as these which have a center sequence whose Hamming distance from any of the alignment rows is at most k, and their determination in the general case is known to be NP-hard.", 
    "editor": [
      {
        "familyName": "B\u00fccher", 
        "givenName": "Philipp", 
        "type": "Person"
      }, 
      {
        "familyName": "Moret", 
        "givenName": "Bernard M. E.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11851561_32", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-39583-6", 
        "978-3-540-39584-3"
      ], 
      "name": "Algorithms in Bioinformatics", 
      "type": "Book"
    }, 
    "keywords": [
      "genomic environment", 
      "gene cluster", 
      "population genetics", 
      "modern genomics", 
      "genetic variation", 
      "DNA sequences", 
      "haplotype blocks", 
      "center sequence", 
      "sequence", 
      "study of variation", 
      "phylogeny", 
      "genomics", 
      "genetics", 
      "variation", 
      "K region", 
      "similarity", 
      "clusters", 
      "alignment", 
      "segments", 
      "environment", 
      "certain degree", 
      "rows", 
      "study", 
      "distance", 
      "detection of segments", 
      "determination", 
      "degree", 
      "important subject", 
      "detection", 
      "block", 
      "instances", 
      "boundaries", 
      "linear time algorithm", 
      "NPs", 
      "framework", 
      "cases", 
      "new linear-time algorithm", 
      "Hamming distance", 
      "subjects", 
      "algorithm", 
      "general case"
    ], 
    "name": "A Linear-Time Algorithm for Studying Genetic Variation", 
    "pagination": "344-354", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028212990"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11851561_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11851561_32", 
      "https://app.dimensions.ai/details/publication/pub.1028212990"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_429.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11851561_32"
  }
]
 

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/11851561_32'

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/11851561_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11851561_32'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11851561_32'


 

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

115 TRIPLES      22 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11851561_32 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author N1064889ca2c743f2b9b20a23e8443be8
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The study of variation in DNA sequences, within the framework of phylogeny or population genetics, for instance, is one of the most important subjects in modern genomics. We here present a new linear-time algorithm for finding maximal k-regions in alignments of three sequences, which can be used for the detection of segments featuring a certain degree of similarity, as well as the boundaries of distinct genomic environments such as gene clusters or haplotype blocks. k-regions are defined as these which have a center sequence whose Hamming distance from any of the alignment rows is at most k, and their determination in the general case is known to be NP-hard.
7 schema:editor N65e57bc3221d4261a5eef4ee40716922
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N9c91766354a34f38a09d26923bbe4f35
11 schema:keywords DNA sequences
12 Hamming distance
13 K region
14 NPs
15 algorithm
16 alignment
17 block
18 boundaries
19 cases
20 center sequence
21 certain degree
22 clusters
23 degree
24 detection
25 detection of segments
26 determination
27 distance
28 environment
29 framework
30 gene cluster
31 general case
32 genetic variation
33 genetics
34 genomic environment
35 genomics
36 haplotype blocks
37 important subject
38 instances
39 linear time algorithm
40 modern genomics
41 new linear-time algorithm
42 phylogeny
43 population genetics
44 rows
45 segments
46 sequence
47 similarity
48 study
49 study of variation
50 subjects
51 variation
52 schema:name A Linear-Time Algorithm for Studying Genetic Variation
53 schema:pagination 344-354
54 schema:productId N326290cbd82b4916905ce6cefdc3d86b
55 N6afd3a9f7fef40d5b031466c4a2c10fe
56 schema:publisher Ne15de0a1ebcd4370b27f5cdd1dbe89ca
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028212990
58 https://doi.org/10.1007/11851561_32
59 schema:sdDatePublished 2022-08-04T17:20
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N32ba4dd87d794bab9f4ee7278f8731a6
62 schema:url https://doi.org/10.1007/11851561_32
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N1064889ca2c743f2b9b20a23e8443be8 rdf:first sg:person.01012555463.19
67 rdf:rest N29bd312ca1df497d8c1e5e1b7afbab49
68 N29bd312ca1df497d8c1e5e1b7afbab49 rdf:first sg:person.01274506210.27
69 rdf:rest rdf:nil
70 N326290cbd82b4916905ce6cefdc3d86b schema:name dimensions_id
71 schema:value pub.1028212990
72 rdf:type schema:PropertyValue
73 N32ba4dd87d794bab9f4ee7278f8731a6 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N6498ef317cd94e8287e43e898584b6aa schema:familyName Moret
76 schema:givenName Bernard M. E.
77 rdf:type schema:Person
78 N65e57bc3221d4261a5eef4ee40716922 rdf:first Nb6e0bba0cf544c99b89d27c900947069
79 rdf:rest Nf5c0d79cc2184603be69913e059922f2
80 N6afd3a9f7fef40d5b031466c4a2c10fe schema:name doi
81 schema:value 10.1007/11851561_32
82 rdf:type schema:PropertyValue
83 N9c91766354a34f38a09d26923bbe4f35 schema:isbn 978-3-540-39583-6
84 978-3-540-39584-3
85 schema:name Algorithms in Bioinformatics
86 rdf:type schema:Book
87 Nb6e0bba0cf544c99b89d27c900947069 schema:familyName Bücher
88 schema:givenName Philipp
89 rdf:type schema:Person
90 Ne15de0a1ebcd4370b27f5cdd1dbe89ca schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nf5c0d79cc2184603be69913e059922f2 rdf:first N6498ef317cd94e8287e43e898584b6aa
93 rdf:rest rdf:nil
94 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
95 schema:name Biological Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
98 schema:name Genetics
99 rdf:type schema:DefinedTerm
100 sg:person.01012555463.19 schema:affiliation grid-institutes:grid.267315.4
101 schema:familyName Stojanovic
102 schema:givenName Nikola
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01012555463.19
104 rdf:type schema:Person
105 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
106 schema:familyName Berman
107 schema:givenName Piotr
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
109 rdf:type schema:Person
110 grid-institutes:grid.267315.4 schema:alternateName Department of Computer Science and Engineering, The University of Texas at Arlington, Arlington, Texas, USA
111 schema:name Department of Computer Science and Engineering, The University of Texas at Arlington, Arlington, Texas, USA
112 rdf:type schema:Organization
113 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA
114 schema:name Department of Computer Science and Engineering, The Pennsylvania State University, University Park, Pennsylvania, USA
115 rdf:type schema:Organization
 




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


...