当前位置:首页 > 新闻中心 > 学术活动

徐金辉系列学术报告预报3

发布日期:2017-07-20

报告人简介:

专长和学术成就:算法设计,计算几何,组合优化,及他们在医学图像,治疗规划,及诊断 ,生物 , 网络与移动计算,大规模集成电路设计 等方面的应用。在这些方向的国际期刊和会议上发表了140余篇论文,大部分出现在国际顶级期刊和会议中。解决了几个长期公开的问题和猜想。推广了一类最基本的几何结构和经典问题。

工作单位及主要简历:于1992年和1995获得中国科技大学,计算机科学本科和硕士学位。于2000年获得美国圣母大学(University of Notre Dame)计算机科学与工程博士学位。同年获美国纽约州立大学(布法罗)计算机科学与工程系助理教授职位,现为该系终身正教授。

 

1. Title: Gauging Association Patterns of Chromosome Territories via Chromatic Median

  报告时间:2015年7月25日下午14:00

  报告地点:理工楼555

 

Abstract: Computing accurate and robust organizational patternsof chromosome territories inside the cell nucleus is criticalfor understanding several fundamental genomic processes,such as co-regulation of gene activation, gene silencing, Xchromosome inactivation, and abnormal chromosome rearrangementin cancer cells. The usage of advanced fluorescencelabeling and image processing techniques has enabledresearchers to investigate interactions of chromosometerritories at large spatial resolution. The resulting highvolume of generated data demands for high-throughput andautomated image analysis methods. In this paper, we introducea novel algorithmic tool for investigating associationpatterns of chromosome territories in a population of cells.Our method takes as input a set of graphs, one for each cell,containing information about spatial interaction of chromosometerritories, and yields a single graph that contains essentialinformation for the whole population and stands asits structural representative. We formulate this combinatorialproblem as a semi-definite programming and presentnovel techniques to efficiently solve it. We validate our approachon both artificial and real biological data; the experimentalresults suggest that our approach yields a near-optimalsolution, and can handle large-size datasets, whichare significant improvements over existing techniques.

 

2.报告题目: On the Connectivity Preserving Minimum Cut Problem

  报告时间:2015年7月28日下午14:00

  报告地点:理工楼555

 

Abstract:In this paper, we study a generalization of the classical minimum cut problem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). For this problem, we consider two variants, connectivity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be approximated within alog(n) for some constant a unless P=NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. For CPMEC, we show that it is in P for planar graphs.