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-09-02T16:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_83.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 N3e8bc2d2fdac443cbe74bb42dbb2ff8c
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 N0468e429a1c74b24904ed11de174d785
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N9a0e266d7e6a4951a890ad86af28a8bf
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 N2af2e1d2ef50467bb2a7994e3c02f3b6
65 Na746ce8d72164d11878632f5d763c876
66 schema:publisher N0983d6874a5c44b8aae8463ae4f30fba
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-09-02T16:17
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher Nd101ce988ec643fea5c092ce88508932
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 N02b6ad24be4044668a20aa49d95863f3 rdf:first N55abd79c6f474c1eb38144186c6d4824
77 rdf:rest rdf:nil
78 N0468e429a1c74b24904ed11de174d785 rdf:first N8d64e85199ad4257ab168288a9037e83
79 rdf:rest N32cb5a7cf7414f65a9e9f9b2cf4c071a
80 N0983d6874a5c44b8aae8463ae4f30fba schema:name Springer Nature
81 rdf:type schema:Organisation
82 N187adb399cf64b5e9d13ddd5fd709dbb rdf:first sg:person.01050464523.69
83 rdf:rest N71244e10697249f29d796834b91b34b1
84 N2af2e1d2ef50467bb2a7994e3c02f3b6 schema:name dimensions_id
85 schema:value pub.1051385616
86 rdf:type schema:PropertyValue
87 N32cb5a7cf7414f65a9e9f9b2cf4c071a rdf:first N459f5f582ea448649c1e6aa1620ad9c6
88 rdf:rest Ndf469f618ed14dd0b5265eac731ec324
89 N3e8bc2d2fdac443cbe74bb42dbb2ff8c rdf:first sg:person.0607503176.22
90 rdf:rest N7293ee66edcd48fb95acadaa72c6dfe9
91 N459f5f582ea448649c1e6aa1620ad9c6 schema:familyName Jiang
92 schema:givenName Rui
93 rdf:type schema:Person
94 N55abd79c6f474c1eb38144186c6d4824 schema:familyName Zhang
95 schema:givenName Xuegong
96 rdf:type schema:Person
97 N71244e10697249f29d796834b91b34b1 rdf:first sg:person.01336557015.68
98 rdf:rest Ne992f4b8b723453c96e69094377f8b12
99 N7293ee66edcd48fb95acadaa72c6dfe9 rdf:first sg:person.0670123347.84
100 rdf:rest N187adb399cf64b5e9d13ddd5fd709dbb
101 N8d64e85199ad4257ab168288a9037e83 schema:familyName Deng
102 schema:givenName Minghua
103 rdf:type schema:Person
104 N9a0e266d7e6a4951a890ad86af28a8bf schema:isbn 978-3-642-37194-3
105 978-3-642-37195-0
106 schema:name Research in Computational Molecular Biology
107 rdf:type schema:Book
108 Na746ce8d72164d11878632f5d763c876 schema:name doi
109 schema:value 10.1007/978-3-642-37195-0_7
110 rdf:type schema:PropertyValue
111 Nb8e25acc59d941f2ae6701a6f0839209 schema:familyName Sun
112 schema:givenName Fengzhu
113 rdf:type schema:Person
114 Nd101ce988ec643fea5c092ce88508932 schema:name Springer Nature - SN SciGraph project
115 rdf:type schema:Organization
116 Ndf469f618ed14dd0b5265eac731ec324 rdf:first Nb8e25acc59d941f2ae6701a6f0839209
117 rdf:rest N02b6ad24be4044668a20aa49d95863f3
118 Ne992f4b8b723453c96e69094377f8b12 rdf:first sg:person.01014741640.26
119 rdf:rest rdf:nil
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)


...