Topics and preliminary list of papers

I. Genome Assembly

Pevzner PA, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53.

*Myers EW. The fragment assembly string graph. Bioinformatics. 2005 Sep 1;21 Suppl 2:ii79-ii85.

II. Genome Rearrangements

The study of rearrangements of large genomic segments that occur during evolution yields a number of algorithmic challenges. Algorithms are based on finding parsimonious sequences of rearrangement operations that transform one permutation into another.

A. Inversions and Translocations

Pevzner, P. 2000. Computational molecular biology: an algorithmic approach. MIT Press, Cambridge, Mass. (Chapter 7)

B. Reversal Distance and Phylogenetic Trees

*Bourque G, Pevzner PA. Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res. 2002 Jan;12(1):26-36.

Chaisson MJ, Raphael BJ, Pevzner PA. Microinversions in mammalian evolution. Proc Natl Acad Sci U S A. 2006 Dec 26;103(52):19824-9.

*Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, Blanchette M, Haussler D, Miller W. Reconstructing contiguous regions of an ancestral genome. Genome Res. 2006 Dec;16(12):1557-65.

C. Deletions and Insertions

*Marron, M., Swenson, K.M., and Moret, B.M.E., "Genomic distances under deletions and insertions," Theoretical Computer Science 325, 3 (2004), 347-360

D. Duplications

*N. El-Mabrouk. Reconstructing an ancestral genome using minimum segments duplications and reversals. Journal of Computer and System Sciences, Vol. 65, pp. 442-464, 2002.

E. General operations

*Alekseyev M. and Pevzner, P. Whole Genome Duplications, Multi-Break Rearrangements, and Genome Halving Problem. SODA 2007

III. Cancer Genomics

A. Experimental methods for measuring alterations in cancer genomes including comparative genomic hybridization (CGH) and end sequence profiling (ESP).

Albertson, D.G., C. Collins, F. McCormick, and J.W. Gray. 2003. Chromosome aberrations in solid tumors. Nat Genet 34: 369-376.

Pinkel, D. and D.G. Albertson. 2005. Array comparative genomic hybridization and its applications in cancer. Nat Genet 37 Suppl: S11-17

Development of computational methods for analyzing this data

Fridlyand, J., et al. 2004. Hidden Markov models approach to the analysis of array CGH data. Journal of Multivariate Analysis 90: 132-153.

Lai WR, Johnson MD, Kucherlapati R, Park PJ. Comparative analysis of algorithms for identifying amplifications and deletions in array CGH data. Bioinformatics. 2005 Oct 1;21(19):3763-70. Epub 2005 Aug 4.

ESP Raphael BJ, Volik S, Collins C, Pevzner PA. Reconstructing tumor genome architectures. Bioinformatics. 2003 Oct;19 Suppl 2:II162-II171.

Raphael B, Pevzner P. Reconstructing tumor amplisomes. Bioinformatics. 2004 Aug 4;20 Suppl 1:I265-I273.

Models of Cancer Progression

Hoglund M, Frigyesi A, Sall T, Gisselsson D, Mitelman F. Statistical behavior of complex cancer karyotypes. Genes Chromosomes Cancer. 2005 Apr;42(4):327-41.

Desper R, et al. Distance-based reconstruction of tree models for oncogenesis. J Comput Biol. 2000;7(6):789-803.

Desper R, et al. Inferring tree models for oncogenesis from comparative genome hybridization data. J Comput Biol. 1999 Spring;6(1):37-51.

*Beerenwinkel N, et al. Learning multiple evolutionary pathways from cross-sectional data. J Comput Biol. 2005 Jul-Aug;12(6):584-98.

*Hjelm M, Hoglund M, Lagergren J. New probabilistic network models and algorithms for oncogenesis. J Comput Biol. 2006 May;13(4):853-65

III. Structural Variation

Introduction to SNPs and haplotypes. Human structural variation.

Feuk L, Carson AR, Scherer SW. Structural variation in the human genome. Nat Rev Genet. 2006 Feb;7(2):85-97. Review.

A. Deletion polymorphisms and SNPs

McCarroll SA, et al. Common deletion polymorphisms in the human genome. Nat Genet. 2006 Jan;38(1):86-92.

Corona E., Raphael, Eskin. Identification of Deletion Polymorphisms from Haplotypes. RECOMB 2007.

Redon R, et al. Global variation in copy number in the human genome. Nature. 2006 Nov 23;444(7118):444-54.


Stefansson H, et al. A common inversion under selection in Europeans. Nat Genet. 2005 Feb;37(2):129-37.

Bansal V, Bashir A, Bafna V. Evidence for large inversion polymorphisms in the human genome from HapMap data. Genome Res. 2006 Dec 21; [Epub ahead of print]

Structural Variants and selection

Sabeti PC, et al. Positive natural selection in the human lineage. Science. 2006 Jun 16;312(5780):1614-20. Review.

Navarro A, Barton NH. Chromosomal speciation and molecular divergence--accelerated evolution in rearranged chromosomes. Science. 2003 Apr 11;300(5617):321-4.

Navarro A, Barbadilla A, Ruiz A. Effect of inversion polymorphism on the neutral nucleotide variability oflinked chromosomal regions in Drosophila. Genetics. 2000 Jun;155(2):685-98.

Protein and regulatory networks

Modeling cellular machinery through biological network comparison Roded Sharan and Trey Ideker Nat Biotech 24 (4), 427-33 (Apr 2006)

A. Network alignment

Kelley BP, et al. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc Natl Acad Sci U S A. 2003 Sep 30;100(20):11394-9.

Conserved patterns of protein interaction in multiple species Roded Sharan et al. Proceedings of the National Academy of Sciences 102 (6), 1974-9 (08 Feb 2005)

*Sharan R, Ideker T, Kelley B, Shamir R, Karp RM. Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. J Comput Biol. 2005 Jul-Aug;12(6):835-46.

*Graemlin: General and robust alignment of multiple large interaction networks -- Flannick et al. Genome Research 16 (9): 1169 (2006)

IV. Network motifs

Efficient algorithms for finding conserved, dense subgraphs in large graphs.

Local graph alignment and motif search in biological networks Johannes Berg and Michael Lassig. Proceedings of the National Academy of Sciences 101 (41), 14689-94 (12 Oct 2004)

Koyuturk M, Kim Y, Subramaniam S, Szpankowski W, Grama A. Detecting conserved interaction patterns in biological networks. J Comput Biol. 2006 Sep;13(7):1299-322.

Network motif identification in stochastic networks Rui Jiang et al. Proceedings of the National Academy of Sciences 103 (25), 9404-9 (20 Jun 2006)