Home


Research


Teaching


Contacts



  University at Buffalo (SUNY)


Dept. of Comp. Sci. and Eng.


Research Projects on the Organization and Spatial Positioning of Cell Nucleus 

  •     Project Summary: Recent research in cell biology has led to the emerging view that the 3-D arrangement of chromosome territories (CT) and the spatial positioning of genes within these territories are linked to genomic function and regulation. Despite this progress, it is not clear what is the spatial organization patterns of CTs inside the cell nucleus and how such patterns dynamically change during the cell cycle and at different stages of cell differentiation and cancer progression. To facilitate more in-depth studies of these important biological problems, in this project we propose to develop a set of efficient algorithmic techniques for determining the patterns and their alterations of three chromosome organization problems: (1) How are chromosomes spatially positioned inside the nucleus? (2) How are chromosomes neighboring or associating with each other? (3) What is the internal structure of each individual chromosome? The core of this project is to develop efficient algorithms for solving a set of challenging computational problems which are essential for the chromosome organization problems.


  •     Project Summary: Spatial positioning has emerged as a fundamental principle governing nuclear processes. Research on chromosome territories has indicated that the 3-D arrangement of these territories within the architecture of the cell nucleus may be closely linked to genomic function, regulation and cell differentiation. Despite this progress, the degree of non-random arrangement of chromosome territories (CT) remains unclear and no overall model at the global level has been proposed. In addition our understanding of gene positioning in chromosome territories in relationship to gene expression is still in its infancy. In this project, we propose to develop algorithmic tools to facilitate the study of three important spatial positioning problems: (1) Topology of chromosome territory; (2) Chromosomes associations and spatial positioning; (3) Topological structures of associated chromosomes territories, and the related segmentation problems.The core of this project is to develop efficient algorithms for solving several challenging computational problems which are essential for the spatial positioning problems.

     


  •     Project Summary: In the post genome era, one of the most challenging tasks is to understand the coordination of overall genomic expression. This requires us to understand how the linear array of genes is arranged along the chromosomes and expressed in the 3D context of the cell nucleus. An effective approach for this problem is to determine the organization and dynamics of the cell nucleus over the cell cycle. Current research on this problem lacks the necessary mathematical models, as well as the automatic tools necessary for large data sets. In this project, we propose to develop a set of algorithmic tools to facilitate the study of three important biological problems: (a) Chromosome organization; (b) Dynamics of chromatin domains in the nucleus of living cells; (c) Mobility properties of functional sites (such as replication and transcription sites). The core of this project is to use computational geometry and optimization techniques to develop efficient algorithms for solving a set of challenging computational problems.


Publications Resulting from the Projects


  • "Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance," with H. Ding and J. Gao. Accepted to the 32nd International Symposium on Computational Geometry (SoCG 2016) , June 14-18, 2016, Boston, USA
  • "Large Scale Probabilistic 3-D Organization of Human Chromosome Territories," with N. Sehgal, A. J. Fritz, J. Vecerova, H. Ding, Z. Chen, B. Stojkovic, S. Bhattacharya, and R. Berezney. Human Molecular Genetics, Vol. 25, No. 3, pp.419-436, 2016. ( Awarded Cover Page and Lead Article; Recommended by F1000Prime as an Article of Special Significance to its Field )
  • "Reorganization of the Interchromosomal Network during Keratinocyte Differentiation," with N. Sehgal, B. Seifert, H. Ding, Z. Chen, B. Stojkovic, S. Bhattacharya, and R. Berezney. Accepted to Chromosoma, 2015.
  • "Chromatic Kernel and Its Applications," with H. Ding, B. Stojkovic, Z. Chen, A. Hughes, L. Xu, A. Fritz, N. Sehgal, and R. Berezney. Accepted to Journal of Combinatorial Optimization, 2015.
  • "Mining k-Median Chromosome Association Graphs from a Population of Hetero- geneous Cells," with Z. Chen, H. Ding, D. Chen, X. Wang, A. Fritz, N. Sehgal, and R. Berezney. Proc. 6th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB 2015).pp.47-56, Sept. 9-12, 2015, Atlanta, GA, USA.
  • "Clustering-Based Collaborative Filtering for Link Prediction," with X. Wang, D. He, and D. Chen. Proc. 29th AAAI Conference on Artificial Intelligence (AAAI 2015).pp.332-338, January 25-29,2015, Austin, Texas, USA.
  • "Random Gradient Descent Tree: A Combinatorial Approach for SVM with Outliers," with H. Ding. Proc. 29th AAAI Conference on Artificial Intelligence (AAAI 2015).pp. 2561-2567, January 25-29, 2015 , Austin, Texas, USA.
  • "A Unified Framework for Clustering Constrained Data without Locality Property," with H. Ding. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).pp. 1471-1490, January 4-6,2015, San Diego, California, USA.
  • "Non-random Patterns in the Distribution of NOR-bearing Chromosome Territories in Human Fibroblasts: A Network Model of Interactions," with A. Pliss, A. J. Fritz, B. Stojkovic, H. Ding, L. Mukherjee, S. Bhattacharya, and R. Berezney. Journal of Cellular Physiology, 230(2), pp.427-439, 2015. ( Awarded Cover Page)
  • "Gene Density and Chromosome Territory Shape," with N. Sehgal, A. J. Fritz, K. Morris, I. Torres, Z. Chen, and R. Berezney. Chromosoma, 123(5), pp.499-513, 2014.
  • "Cell Type Specific Alterations in Interchromosomal Networks Across the Cell Cycle," with A. J. Fritz, B. Stojkovic, H. Ding, S. Bhattacharya, and R. Berezney. PLoS Computational Biology, 10(10), 2014.
  • "Wide-scale Alterations in Interchromosomal Organization in Breast Cancer Cells: Defining a Network of Interacting Chromosomes," with A.J. Fritz, B. Stojkovic, H. Ding, S. Bhattacharya, D. Galle, and R. Berezney. Human Molecular Genetics, 23(19), pp.5133-5146, 2014.
  • "Finding Median Point-Set Using Earth Mover's Distance," with H. Ding. Proc. 28th AAAI conference on Artificial Intelligence (AAAI 2014).pp.1781-1787, July 27-31,2014, Quebec City, Quebec, Canada.
  • "On the Connectivity Preserving Minimum Cut Problem," with Q. Duan. Journal of Computer and System Sciences. 80(4):837-848,2014.
  • "Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems," with H. Ding. Proc. 30th ACM Annual Symposium on Computational Geometry (SoCG 2014) , pp.110-119, June 8-11, 2014, Kyoto, Japan
  • "k-Prototype Learning for 3D Rigid Structures," with H. Ding, and R. Berezney. Advances in Neural Information Processing Systems (NIPS 2013), pp. 2589-2597, December 5-8, 2013, Lake Tahoe, Nevada, USA
  • "On Clustering Induced Voronoi Diagrams," with D.Z. Chen, Z. Huang, and Y. Liu. Proc. 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 390-399, October 27 – 29, 2013, Berkeley, California, USA
  • "FPTAS for Minimizing Earth Mover’s Distance under Rigid Transformations," with H. Ding. Proc. 21st European Symposium on Algorithms (ESA 2013), pp.397-408, Sept. 2-4, 2013, Sophia Antipolis, France
  • "Gauging Association Patterns of Chromosome Territories via Chromatic Median," with H. Ding, B. Stojkovic, and R. Berezney. Proc. 2013 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2013), Oral Presentation, pp. 1296-1303, June 25-27, 2013, Portland, Oregon, USA
  • Y. Zhu and J. Xu, “Improved Algorithms for Farthest Colored Voronoi Diagram of Segments.”  Theoretical Computer Science. 497:20-30, 2013.
  • Y. Zhu and J. Xu, “On the Central Path Problem.” Proc. 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA’12), pp. 135-150, August 5-9, 2012, Banff, Canada.
  • Y. Zhu and J. Xu, “On the 2-Central Path Problem.” Proc. 18th Annual International Computing and Combinatorics Conference (COCOON 2012), pp.543-555, August 20-22, 2012, Sydney, Australia.
  • L. Xu, B. Stojkovic, H. Ding, Q. Song, X. Wu, M. Sonka, and J. Xu, “Efficient Searching of Globally Optimal and Smooth Multisurfaces with Shape Priors” Proc. SPIE Symposium on Medical Imaging (2012) 8314, 83140N, Feb. 6-9, 2012, San Diego, California, USA
  • H. Ding and J. Xu, Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere”, Proc. 38th International Colloquium on Automata, Languages and Programming (ICALP11), pp. 773-784, July 4-8, 2011, Zurich, Switzerland.
  • L. Xu, B. Stojkovic, Y. Zhu, Q. Song, X. Wu, M. Sonka, and J. Xu, Efficient Algorithms for Segmenting Globally Optimal and Smooth Multi-Surfaces, Proc. 22nd biennial International Conference on Information Processing in Medical Imaging (IPMI 11), pp. 208-220, Monastery Irsee, Germany, July 3-8, 2011.
  • Y. Zhu and J. Xu, “Improved Algorithms for Farthest Colored Voronoi Diagram of Segments,” Proc. 5th Annual International Conference on Combinatorial Optimization and Applications(COCOA”11), pp.372-386, August 4-6, 2011, Zhangjiajie, China.
  • L. Xu, B. Stojkovic, H. Ding, Q. Song, X. Wu, M. Sonka, and J. Xu, “Faster Segmentation Algorithm for Optical Coherence Tomography Images with Guaranteed Smoothness.” Proc. 2nd International Workshop: Machine Learning in Medical Imaging (Conjunction with MICCAI 2011), LNCS 7009, pp 308-316, Sept. 18, 2011, Toronto, Canada.
  • J. Xu, L. Xu, and Y. Xie, Approximating Minimum Bending Energy Path in a Simple Corridor, Proc. 21st International Symposium on Algorithms and Computation (ISAAC10), pp. 328-339, Dec. 15-17, Jeju Island, Korea.
  • V. Singh, L. Mukherjee, J. Peng, and J. Xu, “Ensemble Clustering Using Semidefinite Programming with Applications.” Machine Learning, Vol.79 No.1-2, pp. 177-200, 2010
  • M. Lin, Y. Yang, and J. Xu, “Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems.” Algorithmica, 57(2):232-251, 2010
  • J. Xu, Y. Yang, Y. Zhu, and N. Katoh, “A Geometric Spanner of Segments.”  International Journal of Computational Geometry and Applications, 20(1): 43-67, 2010.
  • B. Stojkovic, Y. Zhu, J. Xu, A. Fritz, M. J. Zeitz, R. Berezney, “Computing Maximum Association Graph in Microscopic Nucleus Images,” Proc. 13th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI’10), pp. 530-537, September 20-24, 2010, Beijing, China.
  • M. Lin, Y. Yang, and J. Xu, “On Lazy Bin Packing and Covering Problem.” Theoretical Computer Science, 411(1): 277-284, 2010.
  • G. Xu and J. Xu, “Efficient Approximation Algorithms for Clustering Point-Sets.”   Computational Geometry: Theory and Applications, Vol. 43 , No. 1, pp. 59-66, 2010.
  • P.B. No ̈el, Jinhui Xu, J. Corso, A. M. Walczak, K. R. Hoffmann, S. Schafer, “GPU-Based Cone Beam Computed Tomography.” Computer Methods and Programs in Biomedicine, 98(3):271-277, 2010.
  • J. Xu, L. Xu, and E. Papadopoulou, “Computing the Map of Geometric Minimal Cuts.” Proc. 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, pp. 244-254, December 16-18, 2009, Hawaii, USA.
  • L. Mukherjee, V. Singh, J. Peng, J. Xu, M. J. Zeitz, and R. Berezney, “ Generalized Median Graphs and Applications.” Journal of Combinatorial Optimization, Vol.17, pp. 21-44, 2009
  • M.J. Zeitz, . L. Mukherjee, J. Xu, S. Bhattacharya and R. Berezney, “A Probabilistic Model for the Arrangement of a Subset of Chromosome Territories in WI38 Human Fibroblasts.” Journal of Cellular Physiology, Vol.221, pp. 120-129, 2009. (Awarded Cover Page)
  • P.B. Noel, J. Xu, K. R. Hoffmann, J. Corso, S. Schafer and A. M. Walczak, “High contrast artifact reduction in Cone Beam Computed Tomography by using Geometric Techniques.” Proc. SPIE Conference on Medical Imaging 2009, Volume 7258, pp. 72583A- 72583A-7, Feb. 7-12, 2009, Orlando, Florida, USA.
  • P.B. Noel, J. Corso, J. Xu, K. R. Hoffmann, S. Schafer and A. M. Walczak, “Reconstruction from an exible number of projections in cone-beam computed tomography via active shape models,” Proc. SPIE Conference on Medical Imaging 2009, Volume 7259, pp. 725949-725949-7, Feb. 7-12, 2009, Orlando, Florida, USA.
  • N. V. Marella, S. Bhattacharya, L. Mukherjee , J. Xu and R. Berezney, “Cell Type Specific Chromosome Territory Organization in the Interphase Nucleus of Normal and Cancer Cells.” Journal of Cellular Physiology, Vol.221, pp. 130-138, 2009
  • Marella, NV, Seifert, B., Nagarajan, P, Sinha, S. and Berezney, R. Chromosomal rearrangements during human epidermal keratinocyte differentiation. J Cell Physiol, 2009. 221: 139-146.
  • G. Xu and J. Xu, “An Improved Approximation Algorithm for Facility Location Problem with Penalties.” Journal of Combinatorial Optimization, 17:424-436, 2009
  • K. S. Malyavantham, S. Bhattacharya, M. Barbeitos, L. Mukherjee, J. Xu, F. O. Fackelmayer and R. Berezney, “Identifying Functional Neighborhoods within the Cell Nucleus: Proximity Analysis of Early S-Phase Replicating Chromatin Domains to Sites of Transcription, RNA Polymerase II, HP1γ, Matrin 3 and SAF-A”. Journal of Cellular Biochemistry, Vol.105, pp. 391-403, 2008.
  • Y. Zhu, J. Xu, Y. Yang, N. Katoh, and S. Tanigawa, “Geometric Spanner of Objects under L1 Distance.” Proc. 14th Annual International Computing and Combinatorics Conference (COCOON’08), pp. 395-404, June 27-29, 2008, Dalian, China.
  • V. Singh, L. Mukherjee, P. Dinu, J. Xu, and K.R. Hoffmann, “Limited View CT Reconstruction via Constrained Metric Labelling.” Computer Vision and Image Understanding, 112(1): 67-80, 2008.
  • V. Singh, L. Mukherjee, J. Peng, and J. Xu, “Ensemble Clustering Using Semidefinite Programming.” Proc. 21st Annual Conference on Neural Information Processing Systems (NIPS’07), Dec. 3-5, 2007, Vancouver, B.C., Canada.
  • L. Mukherjee, V. Singh, J. Peng, J. Xu, M. Zeitz, and R. Berezney, “Generalized Median Graphs: Theory and Applications.” Proc. 11th IEEE International Conference on Computer Vision (ICCV’07), Rio De Janeiro, Brazil, Oct. 14-20, 2007.
  • V. Singh, L. Mukherjee, J. Xu, K. R. Hoffmann, P. M. Dinu, and M. Podgorsak, “Brachytherapy Seed Localization Using Geometric and Linear Programming Techniques.” IEEE Transaction on Medical Imaging, Vol. 26, No. 9, pp. 1291-1304, 2007.
  • Y. Yang, Y. Zhu, J. Xu, and N. Katoh, “Geometric Spanner of Segments.” Proc. 18th International Symposium on Algorithms and Computation (ISAAC’07), LNCS 4835, Springer, pp. 75-87, Dec. 17-19, 2007, Sendai, Japan.
  • P.B. Noel, J. Xu, K.R. Hoffmann, V. Singh, S. Schafer, and A.M. Walczak, “Linear Programming Approach to Optimize 3D Data Obtained from Multiple View Angiograms,” Proc. SPIE Symposium on Medical Imaging 2007: Physiology, Function, and Structure from Medical Images, Vol. 6511, No. 1, pages 65112F, numpages 9, Feb. 17-22, 2007, San Diego, California, USA.
  • L. Mukherjee, V. Singh, J. Xu, R. Berezney, “Fitting Polygonal Regions for Matching 3D Polyhedra.” Proc. of IS&T/SPIE International Symposium on Electronic Imaging: Vision Geometry XIV, Volume 6066, pages 606607, numpages 12, Jan. 15-19, 2006, San Jose, California, USA.
  • L. Mukherjee, V.Singh, J. Xu, K.R. Malyavantham, and R. Berezney, “On Mobility Analysis of Functional Sites from Time Lapse Microscopic Image Sequence of Living Cell Nucleus.” Proc. 9th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI’06), pp. 577-585, Copenhagen, Denmark, Oct. 1-6, 2006
  • L. Mukherjee, M. Lin, J. Xu, and R. Berezney, “Motion Tracking and Intensity Surface Recovery in Microscopic Nuclear Images.” Proc. the 8th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI 2005), LNCS 3749, page 876-884, Palm Springs, California, USA, Oct. 26 to Oct 29, 2005.


Resulting Software Package


  • A software package called Algorithmic Toolbox is under development. The package provides practical solutions for a wide range of problems (such as chromosome associations, chromosome topology, gene spatial distribution patterns, chromosome spatial positioning, etc.) stemming from the study of spatial positioning and organization of the cell nucleus.


Last modified:

August 2006