Phenotype space and kinship assignment for the Simpson index

Bruce Litow; Dmitry Konovalov

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 2, page 323-333
  • ISSN: 0988-3754

Abstract

top
We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype space size. This algorithm is based on a relaxed version of the assignment problem, where fractional assignments (over the reals) are permitted.

How to cite

top

Litow, Bruce, and Konovalov, Dmitry. "Phenotype space and kinship assignment for the Simpson index." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 323-333. <http://eudml.org/doc/245441>.

@article{Litow2008,
abstract = {We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype space size. This algorithm is based on a relaxed version of the assignment problem, where fractional assignments (over the reals) are permitted.},
author = {Litow, Bruce, Konovalov, Dmitry},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {population biology; kinship assignment complexity; Tarski algebra; phenotype space},
language = {eng},
number = {2},
pages = {323-333},
publisher = {EDP-Sciences},
title = {Phenotype space and kinship assignment for the Simpson index},
url = {http://eudml.org/doc/245441},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Litow, Bruce
AU - Konovalov, Dmitry
TI - Phenotype space and kinship assignment for the Simpson index
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2008
PB - EDP-Sciences
VL - 42
IS - 2
SP - 323
EP - 333
AB - We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype space size. This algorithm is based on a relaxed version of the assignment problem, where fractional assignments (over the reals) are permitted.
LA - eng
KW - population biology; kinship assignment complexity; Tarski algebra; phenotype space
UR - http://eudml.org/doc/245441
ER -

References

top
  1. [1] A. Almudevar, A simulated annealing algorithm for maximum likelihood pedigree reconstruction. Theor. Popul. Biol. 63 (2003) 63–75. Zbl1104.62115
  2. [2] A. Almudevar and C. Field, Estimation of single-generation sibling relationships based on dna markers. J. Agr. Biol. Envir. St. 4 (1999) 136–165. MR1812079
  3. [3] S. Basu, R. Pollack and M-F. Roy, Algorithms in Real Algebraic Geometry. Springer (2005). Zbl1102.14041MR1998147
  4. [4] T.Y. Berger-Wolf, B. DasGupta, W. Chaovalitwongse and M. Ashley, Combinatorial reconstructions of sibling relationships. In 6th International Symposium on Computational Biology and Genome Informatics (CBGI), Salt Lake City, Utah (2005) 1252–1255. 
  5. [5] G. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Automata theory and formal languages. Springer (1975) 134–183. Zbl0318.02051MR403962
  6. [6] L. Csanky, Fast parallel matrix inversion algorithms. In 16th IEEE FOCS (1975) 11–12. Zbl0353.68063MR428785
  7. [7] H. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic. Springer (1984). Zbl0556.03001MR736838
  8. [8] K.F. Goodnight and D.C. Queller. Computer software for performing likelihood tests of pedigree relationship using genetic markers. Mol. Ecol. 8 (1999) 1231–1234. 
  9. [9] D.Yu. Grigoriev, Complexity of deciding Tarski algebra. J. Symb. Comput. 5 (1988) 65–108. Zbl0689.03021MR949113
  10. [10] N. Jacobson, Basic Algebra, Vol. I. Freeman, 2nd edn. (1985). Zbl0557.16001MR780184
  11. [11] A.G. Jones and W.R. Arden, Methods of parentage analysis in natural populations. Mol. Ecol. 12 (2003) 2511–2523. 
  12. [12] D.A. Konovalov, Accuracy of four heuristics for the full sibship reconstruction problem in the presence of genotype errors. In The Fourth Asia Pacific Bioinformatics Conference, 13-16 Feb, 2006, Taiwan (2006) 7-16. 
  13. [13] D.A. Konovalov, C. Manning and M.T. Henshaw, Kingroup: a program for pedigree relationship reconstruction and kin group assignments using genetic markers. Mol. Ecol. Notes 4 (2004) 779–782. 
  14. [14] D.A. Konovalov, N. Bajema and B. Litow, Modified simpson o(n3) algorithm for the full sibship reconstruction problem. Bioinformatics 21 (2005) 3912–3917. 
  15. [15] D.A. Konovalov, B. Litow and N. Bajema, Partition-distance via the assignment problem. Bioinformatics 21 (2005) 2463–2468. 
  16. [16] B. Mishra, Algorithmic Algebra. Springer (1993). Zbl0804.13009MR1239443
  17. [17] P.T. O’Reilly, C. Herbinger and J.M. Wright, Analysis of parentage determination in atlantic salmon (salmo salar) using microsatellites. Anim. Genet. 29 (1998) 363–370. 
  18. [18] A. Tarski, Sur les ensembles définissables de nombres réels. Fundamenta Mathematicae 17 (1931) 210–239. Zbl57.0060.02JFM57.0060.02
  19. [19] A. Tarski, A decision method for elementary algebra and geometry. Technical report, Rand Corp. (1948). Zbl0035.00602MR28796
  20. [20] J.L. Wang, Sibship reconstruction from genetic data with typing errors. Genetics 166 (2004) 1963–1979. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.