Research output: Contribution to journal › Article

**Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees.** / Sheehan, Nuala; Bartlett, Mark; Cussens, James.

Research output: Contribution to journal › Article

Sheehan, N, Bartlett, M & Cussens, J 2014, 'Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees', *Theoretical Population Biology*, vol. 97, pp. 11-19. https://doi.org/10.1016/j.tpb.2014.07.002

Sheehan, N., Bartlett, M., & Cussens, J. (2014). Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees. *Theoretical Population Biology*, *97*, 11-19. https://doi.org/10.1016/j.tpb.2014.07.002

Sheehan N, Bartlett M, Cussens J. Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees. Theoretical Population Biology. 2014 Nov;97:11-19. https://doi.org/10.1016/j.tpb.2014.07.002

@article{89093c1e1a1f4e259e317f4ea23f4438,

title = "Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees",

abstract = "The reconstruction of pedigrees from genetic marker data is relevant to a wide range of applications. Likelihood-based approaches aim to find the pedigree structure that gives the highest probability to the observed data. Existing methods either entail an exhaustive search and are hence restricted to small numbers of individuals, or they take a more heuristic approach and deliver a solution that will probably have high likelihood but is not guaranteed to be optimal. By encoding the pedigree learning problem as an integer linear program we can exploit efficient optimisation algorithms to construct pedigrees guaranteed to have maximal likelihood for the standard situation where we have complete marker data at unlinked loci and segregation of genes from parents to offspring is Mendelian. Previous work demonstrated efficient reconstruction of pedigrees of up to about 100 individuals. The modified method that we present here is not so restricted: we demonstrate its applicability with simulated data on a real human pedigree structure of over 1600 individuals. It also compares well with a very competitive approximate approach in terms of solving time and accuracy. In addition to identifying a maximum likelihood pedigree, we can obtain any number of pedigrees in decreasing order of likelihood. This is useful for assessing the uncertainty of a maximum likelihood solution and permits model averaging over high likelihood pedigrees when this would be appropriate. More importantly, when the solution is not unique, as will often be the case for large pedigrees, it enables investigation into the properties of maximum likelihood pedigree estimates which has not been possible up to now. Crucially, we also have a means of assessing the behaviour of other approximate approaches which all aim to find a maximum likelihood solution. Our approach hence allows us to properly address the question of whether a reasonably high likelihood solution that is easy to obtain is practically as useful as a guaranteed maximum likelihood solution. The efficiency of our method on such large problems bodes well for extensions beyond the standard setting where some pedigree members may be latent, genotypes may be measured with error and markers may be linked.",

keywords = "Constrained optimisation, Integer linear program, BAYESIAN NETWORKS, Genetic marker data",

author = "Nuala Sheehan and Mark Bartlett and James Cussens",

year = "2014",

month = "11",

doi = "10.1016/j.tpb.2014.07.002",

language = "English",

volume = "97",

pages = "11--19",

journal = "Theoretical Population Biology",

issn = "0040-5809",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees

AU - Sheehan, Nuala

AU - Bartlett, Mark

AU - Cussens, James

PY - 2014/11

Y1 - 2014/11

N2 - The reconstruction of pedigrees from genetic marker data is relevant to a wide range of applications. Likelihood-based approaches aim to find the pedigree structure that gives the highest probability to the observed data. Existing methods either entail an exhaustive search and are hence restricted to small numbers of individuals, or they take a more heuristic approach and deliver a solution that will probably have high likelihood but is not guaranteed to be optimal. By encoding the pedigree learning problem as an integer linear program we can exploit efficient optimisation algorithms to construct pedigrees guaranteed to have maximal likelihood for the standard situation where we have complete marker data at unlinked loci and segregation of genes from parents to offspring is Mendelian. Previous work demonstrated efficient reconstruction of pedigrees of up to about 100 individuals. The modified method that we present here is not so restricted: we demonstrate its applicability with simulated data on a real human pedigree structure of over 1600 individuals. It also compares well with a very competitive approximate approach in terms of solving time and accuracy. In addition to identifying a maximum likelihood pedigree, we can obtain any number of pedigrees in decreasing order of likelihood. This is useful for assessing the uncertainty of a maximum likelihood solution and permits model averaging over high likelihood pedigrees when this would be appropriate. More importantly, when the solution is not unique, as will often be the case for large pedigrees, it enables investigation into the properties of maximum likelihood pedigree estimates which has not been possible up to now. Crucially, we also have a means of assessing the behaviour of other approximate approaches which all aim to find a maximum likelihood solution. Our approach hence allows us to properly address the question of whether a reasonably high likelihood solution that is easy to obtain is practically as useful as a guaranteed maximum likelihood solution. The efficiency of our method on such large problems bodes well for extensions beyond the standard setting where some pedigree members may be latent, genotypes may be measured with error and markers may be linked.

AB - The reconstruction of pedigrees from genetic marker data is relevant to a wide range of applications. Likelihood-based approaches aim to find the pedigree structure that gives the highest probability to the observed data. Existing methods either entail an exhaustive search and are hence restricted to small numbers of individuals, or they take a more heuristic approach and deliver a solution that will probably have high likelihood but is not guaranteed to be optimal. By encoding the pedigree learning problem as an integer linear program we can exploit efficient optimisation algorithms to construct pedigrees guaranteed to have maximal likelihood for the standard situation where we have complete marker data at unlinked loci and segregation of genes from parents to offspring is Mendelian. Previous work demonstrated efficient reconstruction of pedigrees of up to about 100 individuals. The modified method that we present here is not so restricted: we demonstrate its applicability with simulated data on a real human pedigree structure of over 1600 individuals. It also compares well with a very competitive approximate approach in terms of solving time and accuracy. In addition to identifying a maximum likelihood pedigree, we can obtain any number of pedigrees in decreasing order of likelihood. This is useful for assessing the uncertainty of a maximum likelihood solution and permits model averaging over high likelihood pedigrees when this would be appropriate. More importantly, when the solution is not unique, as will often be the case for large pedigrees, it enables investigation into the properties of maximum likelihood pedigree estimates which has not been possible up to now. Crucially, we also have a means of assessing the behaviour of other approximate approaches which all aim to find a maximum likelihood solution. Our approach hence allows us to properly address the question of whether a reasonably high likelihood solution that is easy to obtain is practically as useful as a guaranteed maximum likelihood solution. The efficiency of our method on such large problems bodes well for extensions beyond the standard setting where some pedigree members may be latent, genotypes may be measured with error and markers may be linked.

KW - Constrained optimisation

KW - Integer linear program

KW - BAYESIAN NETWORKS

KW - Genetic marker data

U2 - 10.1016/j.tpb.2014.07.002

DO - 10.1016/j.tpb.2014.07.002

M3 - Article

VL - 97

SP - 11

EP - 19

JO - Theoretical Population Biology

T2 - Theoretical Population Biology

JF - Theoretical Population Biology

SN - 0040-5809

ER -