Genotype Sequence Segmentation: Handling Constraints and Noise Conference Paper uri icon

abstract

  • Recombination plays an important role in shaping the genetic variations present in current-day populations. We consider populations evolved from a small number of founders, where each individual's genomic sequence is composed of segments from the founders. We study the problem of segmenting the genotype sequences into the minimum number of segments attributable to the founder sequences. The minimum segmentation can be used for inferring the relationship among sequences to identify the genetic basis of traits, which is important for disease association studies. We propose two dynamic programming algorithms which can solve the minimum segmentation problem in polynomial time. Our algorithms incorporate biological constraints to greatly reduce the computation, and guarantee that only minimum segmentation solutions with comparable numbers of segments on both haplotypes of the genotype sequence are computed. Our algorithms can also work on noisy data including genotyping errors, point mutations, gene conversions, and missing values. 2008 Springer-Verlag Berlin Heidelberg.

published proceedings

  • ALGORITHMS IN BIOINFORMATICS, WABI 2008

author list (cited authors)

  • Zhang, Q. i., Wang, W., McMillan, L., Prins, J., de Villena, F., & Threadgill, D.

citation count

  • 3

complete list of authors

  • Zhang, Qi||Wang, Wei||McMillan, Leonard||Prins, Jan||de Villena, Fernando Pardo-Manuel||Threadgill, David

publication date

  • January 2008