The use of graph theory techniques to investigate genealogical structure

Cathryn M. Lewis

doi:10.1093/imammb/9.3.145

The use of graph theory techniques to investigate genealogical structure

Cathryn M. Lewis

Research output: Contribution to journal › Article › peer-review

Abstract

The correspondence between a graph and a genealogy is used to apply techniques from the field of graph theory to genetic epidemiology. A method is described for discarding the individuals and marriages which contribute to the size but not to the complexity of a genealogy. The 'max-flow min-cut' algorithm is extended to break large genealogies into two smaller, less complicated components. These techniques are illustrated using both artificial and real pedigrees.

Original language	English
Pages (from-to)	145-159
Number of pages	15
Journal	Mathematical Medicine and Biology
Volume	9
Issue number	3
DOIs	https://doi.org/10.1093/imammb/9.3.145
State	Published - 1992
Externally published	Yes

Keywords

Cutset
Genealogy
Graph
Max-flow
Min-flow
Network

Access to Document

10.1093/imammb/9.3.145

Cite this

@article{7299380e6fa74ce29a0f2b3389cb75a9,

title = "The use of graph theory techniques to investigate genealogical structure",

abstract = "The correspondence between a graph and a genealogy is used to apply techniques from the field of graph theory to genetic epidemiology. A method is described for discarding the individuals and marriages which contribute to the size but not to the complexity of a genealogy. The 'max-flow min-cut' algorithm is extended to break large genealogies into two smaller, less complicated components. These techniques are illustrated using both artificial and real pedigrees.",

keywords = "Cutset, Genealogy, Graph, Max-flow, Min-flow, Network",

author = "Lewis, \{Cathryn M.\}",

note = "Funding Information: Thanks are due to Dr W. C. Knowler for providing the Pima data from the National Institute of Diabetes and Digestive and Kidney Diseases' study of the Gila River Indian Community, to Dr Alun Thomas for providing the Przewalski's horse data, and to Prof. Chris Cannings for useful discussions during this work. This research was carried out whilst the author was supported by a studentship from the Science and Engineering Research Council held at the Department of Probability and Statistics, University of Sheffield.",

year = "1992",

doi = "10.1093/imammb/9.3.145",

language = "English",

volume = "9",

pages = "145--159",

journal = "Mathematical Medicine and Biology",

issn = "1477-8599",

publisher = "Oxford University Press",

number = "3",

}

TY - JOUR

T1 - The use of graph theory techniques to investigate genealogical structure

AU - Lewis, Cathryn M.

N1 - Funding Information: Thanks are due to Dr W. C. Knowler for providing the Pima data from the National Institute of Diabetes and Digestive and Kidney Diseases' study of the Gila River Indian Community, to Dr Alun Thomas for providing the Przewalski's horse data, and to Prof. Chris Cannings for useful discussions during this work. This research was carried out whilst the author was supported by a studentship from the Science and Engineering Research Council held at the Department of Probability and Statistics, University of Sheffield.

PY - 1992

Y1 - 1992

N2 - The correspondence between a graph and a genealogy is used to apply techniques from the field of graph theory to genetic epidemiology. A method is described for discarding the individuals and marriages which contribute to the size but not to the complexity of a genealogy. The 'max-flow min-cut' algorithm is extended to break large genealogies into two smaller, less complicated components. These techniques are illustrated using both artificial and real pedigrees.

AB - The correspondence between a graph and a genealogy is used to apply techniques from the field of graph theory to genetic epidemiology. A method is described for discarding the individuals and marriages which contribute to the size but not to the complexity of a genealogy. The 'max-flow min-cut' algorithm is extended to break large genealogies into two smaller, less complicated components. These techniques are illustrated using both artificial and real pedigrees.

KW - Cutset

KW - Genealogy

KW - Graph

KW - Max-flow

KW - Min-flow

KW - Network

UR - https://www.scopus.com/pages/publications/77957178296

U2 - 10.1093/imammb/9.3.145

DO - 10.1093/imammb/9.3.145

M3 - Article

AN - SCOPUS:77957178296

SN - 1477-8599

VL - 9

SP - 145

EP - 159

JO - Mathematical Medicine and Biology

JF - Mathematical Medicine and Biology

IS - 3

ER -

The use of graph theory techniques to investigate genealogical structure

Abstract

Keywords

Access to Document

Fingerprint

Cite this