IPED: Inheritance Path Based Pedigree Reconstruction Algorithm Using Genotype Data View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Dan He , Zhanyong Wang , Buhm Han , Laxmi Parida , Eleazar Eskin

ABSTRACT

The problem of inference of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Various methods have been proposed to automate the process of pedigree reconstruction given the genotypes or haplotypes of a set of individuals. Current methods, unfortunately, are very time consuming and inaccurate for complicated pedigrees such as pedigrees with inbreeding. In this work, we propose an efficient algorithm which is able to reconstruct large pedigrees with reasonable accuracy. Our algorithm reconstructs the pedigrees generation by generation backwards in time from the extant generation. We predict the relationships between individuals in the same generation using an inheritance path based approach implemented using an efficient dynamic programming algorithm. Experiments show that our algorithm runs in linear time with respect to the number of reconstructed generations and therefore it can reconstruct pedigrees which have a large number of generations. Indeed it is the first practical method for reconstruction of large pedigrees from genotype data. More... »

PAGES

75-87

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-37195-0_7

DOI

http://dx.doi.org/10.1007/978-3-642-37195-0_7

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Dan", 
        "id": "sg:person.0607503176.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0607503176.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Zhanyong", 
        "id": "sg:person.0670123347.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670123347.84"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Program in Medical and Population Genetics, Broad Institute of Harvard and MIT, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.66859.34", 
          "name": [
            "Division of Genetics, Brigham and Women\u2019s Hospital, Harvard Medical School, Boston, MA, USA", 
            "Program in Medical and Population Genetics, Broad Institute of Harvard and MIT, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Han", 
        "givenName": "Buhm", 
        "id": "sg:person.01050464523.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01050464523.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Parida", 
        "givenName": "Laxmi", 
        "id": "sg:person.01336557015.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01336557015.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Eskin", 
        "givenName": "Eleazar", 
        "id": "sg:person.01014741640.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01014741640.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "The problem of inference of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Various methods have been proposed to automate the process of pedigree reconstruction given the genotypes or haplotypes of a set of individuals. Current methods, unfortunately, are very time consuming and inaccurate for complicated pedigrees such as pedigrees with inbreeding. In this work, we propose an efficient algorithm which is able to reconstruct large pedigrees with reasonable accuracy. Our algorithm reconstructs the pedigrees generation by generation backwards in time from the extant generation. We predict the relationships between individuals in the same generation using an inheritance path based approach implemented using an efficient dynamic programming algorithm. Experiments show that our algorithm runs in linear time with respect to the number of reconstructed generations and therefore it can reconstruct pedigrees which have a large number of generations. Indeed it is the first practical method for reconstruction of large pedigrees from genotype data.", 
    "editor": [
      {
        "familyName": "Deng", 
        "givenName": "Minghua", 
        "type": "Person"
      }, 
      {
        "familyName": "Jiang", 
        "givenName": "Rui", 
        "type": "Person"
      }, 
      {
        "familyName": "Sun", 
        "givenName": "Fengzhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Xuegong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-37195-0_7", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-37194-3", 
        "978-3-642-37195-0"
      ], 
      "name": "Research in Computational Molecular Biology", 
      "type": "Book"
    }, 
    "keywords": [
      "pedigree reconstruction", 
      "genotype data", 
      "large pedigree", 
      "pedigree generations", 
      "pedigree", 
      "complicated pedigrees", 
      "inbreeding", 
      "family tree", 
      "genetics", 
      "same generation", 
      "haplotypes", 
      "set of individuals", 
      "trees", 
      "genotypes", 
      "large number", 
      "inheritance path", 
      "individuals", 
      "generation", 
      "current methods", 
      "number", 
      "efficient dynamic programming algorithm", 
      "first practical method", 
      "inference", 
      "dynamic programming algorithm", 
      "group of individuals", 
      "data", 
      "efficient algorithm", 
      "algorithm runs", 
      "programming algorithm", 
      "reconstruction algorithm", 
      "process", 
      "experiments", 
      "algorithm", 
      "fundamental problem", 
      "linear time", 
      "reconstruction", 
      "relationship", 
      "time", 
      "set", 
      "problem of inference", 
      "group", 
      "approach", 
      "respect", 
      "method", 
      "reasonable accuracy", 
      "work", 
      "accuracy", 
      "practical method", 
      "run", 
      "path", 
      "problem"
    ], 
    "name": "IPED: Inheritance Path Based Pedigree Reconstruction Algorithm Using Genotype Data", 
    "pagination": "75-87", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051385616"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-37195-0_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-37195-0_7", 
      "https://app.dimensions.ai/details/publication/pub.1051385616"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_56.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-37195-0_7"
  }
]
 

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-642-37195-0_7'

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-642-37195-0_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-37195-0_7'

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-642-37195-0_7'


 

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

160 TRIPLES      22 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-37195-0_7 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Ne27ff03e17d342afa61f9232e1a9f21e
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description The problem of inference of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Various methods have been proposed to automate the process of pedigree reconstruction given the genotypes or haplotypes of a set of individuals. Current methods, unfortunately, are very time consuming and inaccurate for complicated pedigrees such as pedigrees with inbreeding. In this work, we propose an efficient algorithm which is able to reconstruct large pedigrees with reasonable accuracy. Our algorithm reconstructs the pedigrees generation by generation backwards in time from the extant generation. We predict the relationships between individuals in the same generation using an inheritance path based approach implemented using an efficient dynamic programming algorithm. Experiments show that our algorithm runs in linear time with respect to the number of reconstructed generations and therefore it can reconstruct pedigrees which have a large number of generations. Indeed it is the first practical method for reconstruction of large pedigrees from genotype data.
7 schema:editor N9547d4b277db434fbc38954b5208aeb9
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nde84ed3757f64215aecb12a68f297c74
11 schema:keywords accuracy
12 algorithm
13 algorithm runs
14 approach
15 complicated pedigrees
16 current methods
17 data
18 dynamic programming algorithm
19 efficient algorithm
20 efficient dynamic programming algorithm
21 experiments
22 family tree
23 first practical method
24 fundamental problem
25 generation
26 genetics
27 genotype data
28 genotypes
29 group
30 group of individuals
31 haplotypes
32 inbreeding
33 individuals
34 inference
35 inheritance path
36 large number
37 large pedigree
38 linear time
39 method
40 number
41 path
42 pedigree
43 pedigree generations
44 pedigree reconstruction
45 practical method
46 problem
47 problem of inference
48 process
49 programming algorithm
50 reasonable accuracy
51 reconstruction
52 reconstruction algorithm
53 relationship
54 respect
55 run
56 same generation
57 set
58 set of individuals
59 time
60 trees
61 work
62 schema:name IPED: Inheritance Path Based Pedigree Reconstruction Algorithm Using Genotype Data
63 schema:pagination 75-87
64 schema:productId N35480ac4d95d45a9b545885b6e603555
65 Nc5b3233f954444e0b4cde6c9bdcfcff2
66 schema:publisher N38072ddf03884eb5b99fa85486fee688
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051385616
68 https://doi.org/10.1007/978-3-642-37195-0_7
69 schema:sdDatePublished 2022-12-01T06:54
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher Na9615d5740d745a382b4b13dc44188a1
72 schema:url https://doi.org/10.1007/978-3-642-37195-0_7
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N0137c6e1b69142e898b70615b428bdd2 schema:familyName Sun
77 schema:givenName Fengzhu
78 rdf:type schema:Person
79 N0640baf45f01406eb631ba54d6c87dc1 rdf:first sg:person.01336557015.68
80 rdf:rest N86e5ed514ed9453ca7e2cb5995293d8b
81 N35480ac4d95d45a9b545885b6e603555 schema:name doi
82 schema:value 10.1007/978-3-642-37195-0_7
83 rdf:type schema:PropertyValue
84 N38072ddf03884eb5b99fa85486fee688 schema:name Springer Nature
85 rdf:type schema:Organisation
86 N66cb17ce3005484e8cd7c7a9df8ebf3f rdf:first sg:person.0670123347.84
87 rdf:rest Nb0eec401506f438c833657c5b511ba4b
88 N67772803db8f49499486e10547d9e8c6 rdf:first N0137c6e1b69142e898b70615b428bdd2
89 rdf:rest Nb1bb58e4074a45ebbb4b12dbe7f431bf
90 N86e5ed514ed9453ca7e2cb5995293d8b rdf:first sg:person.01014741640.26
91 rdf:rest rdf:nil
92 N9547d4b277db434fbc38954b5208aeb9 rdf:first Nf994f9c9e1954d51ad9a722ee26ab710
93 rdf:rest Nbf58a2577ae6458fbed6bc97777a6a2f
94 Na9615d5740d745a382b4b13dc44188a1 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 Nb0eec401506f438c833657c5b511ba4b rdf:first sg:person.01050464523.69
97 rdf:rest N0640baf45f01406eb631ba54d6c87dc1
98 Nb1bb58e4074a45ebbb4b12dbe7f431bf rdf:first Ne8e58fff2bdb42ec93e8802cb08f8db9
99 rdf:rest rdf:nil
100 Nbf58a2577ae6458fbed6bc97777a6a2f rdf:first Ne051b7cce7a94a04bd24683a37ac464c
101 rdf:rest N67772803db8f49499486e10547d9e8c6
102 Nc5b3233f954444e0b4cde6c9bdcfcff2 schema:name dimensions_id
103 schema:value pub.1051385616
104 rdf:type schema:PropertyValue
105 Nde84ed3757f64215aecb12a68f297c74 schema:isbn 978-3-642-37194-3
106 978-3-642-37195-0
107 schema:name Research in Computational Molecular Biology
108 rdf:type schema:Book
109 Ne051b7cce7a94a04bd24683a37ac464c schema:familyName Jiang
110 schema:givenName Rui
111 rdf:type schema:Person
112 Ne27ff03e17d342afa61f9232e1a9f21e rdf:first sg:person.0607503176.22
113 rdf:rest N66cb17ce3005484e8cd7c7a9df8ebf3f
114 Ne8e58fff2bdb42ec93e8802cb08f8db9 schema:familyName Zhang
115 schema:givenName Xuegong
116 rdf:type schema:Person
117 Nf994f9c9e1954d51ad9a722ee26ab710 schema:familyName Deng
118 schema:givenName Minghua
119 rdf:type schema:Person
120 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
121 schema:name Mathematical Sciences
122 rdf:type schema:DefinedTerm
123 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
124 schema:name Statistics
125 rdf:type schema:DefinedTerm
126 sg:person.01014741640.26 schema:affiliation grid-institutes:grid.19006.3e
127 schema:familyName Eskin
128 schema:givenName Eleazar
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01014741640.26
130 rdf:type schema:Person
131 sg:person.01050464523.69 schema:affiliation grid-institutes:grid.66859.34
132 schema:familyName Han
133 schema:givenName Buhm
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01050464523.69
135 rdf:type schema:Person
136 sg:person.01336557015.68 schema:affiliation grid-institutes:grid.481554.9
137 schema:familyName Parida
138 schema:givenName Laxmi
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01336557015.68
140 rdf:type schema:Person
141 sg:person.0607503176.22 schema:affiliation grid-institutes:grid.481554.9
142 schema:familyName He
143 schema:givenName Dan
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0607503176.22
145 rdf:type schema:Person
146 sg:person.0670123347.84 schema:affiliation grid-institutes:grid.19006.3e
147 schema:familyName Wang
148 schema:givenName Zhanyong
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670123347.84
150 rdf:type schema:Person
151 grid-institutes:grid.19006.3e schema:alternateName Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA
152 schema:name Department of Computer Science, University of California Los Angeles, 90095, Los Angeles, CA, USA
153 rdf:type schema:Organization
154 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA
155 schema:name IBM T.J. Watson Research, 10598, Yorktown Heights, NY, USA
156 rdf:type schema:Organization
157 grid-institutes:grid.66859.34 schema:alternateName Program in Medical and Population Genetics, Broad Institute of Harvard and MIT, Cambridge, MA, USA
158 schema:name Division of Genetics, Brigham and Women’s Hospital, Harvard Medical School, Boston, MA, USA
159 Program in Medical and Population Genetics, Broad Institute of Harvard and MIT, Cambridge, MA, USA
160 rdf:type schema:Organization
 




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


...