Recombination is an important evolutionary mechanism responsible for the genetic diversity in humans and other organisms. Recently, there has been extensive research on understanding the fine scale variation in recombination rates across the human genome using DNA polymorphism data. A combinatorial approach toward this is to estimate the minimum number of recombination events in any history of the sample. During 2003-2007, I developed several recombination lower bounds on this minimum number of recombination events. We also explored the computational complexity of these lower bounds. The publications that describe this work are listed below:
Vineet Bafna,
Vikas Bansal:
The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds.
IEEE/ACM Trans. Comput. Biology Bioinform. 1(2): 78-90 (2004)
Vineet Bafna,
Vikas Bansal:
Improved Recombination Lower Bounds for Haplotype Data.
RECOMB 2005: 569-584
Vineet Bafna,
Vikas Bansal:
Inference about Recombination from Haplotype Data: Lower Bounds and Recombination Hotspots.
Journal of Computational Biology 13(2): 501-521 (2006)
Dan Gusfield,
Vikas Bansal,
Vineet Bafna,
Yun S. Song:
A Decomposition Theory for Phylogenetic Networks and Incompatible Characters.
Journal of Computational Biology 14(10): 1247-1272 (2007)
The program LUBOUND that calculates the lower bound R_I and the PDFs of several papers describing these lower bounds can be downloaded from the attachments.