Sharon Hüffner

Sharon Bruckner (Hüffner)

I obtained my PhD at the International Max Planck Research School for Computational Biology and Scientific Computing (IMPRS-CBSC) at Freie Universität Berlin.

My PhD research was on network analysis and graph algorithms, in particular fuzzy clustering of networks using spectral analysis, with applications in bioinformatics.

Nowadays, I am working for Nexgate (a division of Proofpoint) as Senior Data Scientist.

Email:

Where I have been in former times

• 2009–2014: PhD in Computer Science in the International Max Planck Research School for Computational Biology and Scientific Computing (IMPRS-CBSC) at the Biocomputing Group (Prof. Christof Schütte) at Freie Universität Berlin.
• 2007–2009: Master in Computer Science at Tel Aviv University, Algorithms in Computational Genomics group (Prof. Ron Shamir)
• 2005–2008: Algorithm Designer at Websense (formerly PortAuthority Technologies)
• 2004–2005: GUI developer and QA engineer at Tidex Systems LTD

You might have met me here

2014-04-24	Graduate seminar of the Machine Learning Group, Hamburg, Germany. Talk: Modularity in Biological Networks.
2013-06-05 – 2013-06-07	12th International Symposium on Experimental Algorithms (SEA 2013), Rome, Italy.	talk (.pptx)
2012-08-23	S4 Security Conference San Francisco, CA. Attended in spirit, gave talk via Skype
2012-08-13 – 2012-08-17	ADFOCS 2012 Summer School, Saarbrucken, Germany.
2012-07-03 – 2012-07-05	23rd Annual Symposium on Combinatorial Pattern Matching (CPM 2012), Helsinki, Finland.	talk (.pdf)
2012-01-19	Research seminar Algorithms and Complexity group, Technische Universität Berlin. Talk: Network-based clustering under heterogeneity constraints
2011-05-02 – 2011-05-05	Annual Meeting of DFG SPP Algorithm Engineering 2011, Berlin, Germany.
2011-03-28 – 2011-03-31	15th Annual International Conference on Research in Computational Molecular Biology (RECOMB ’11), Vancouver, Canada. Poster: Understanding biological networks with the random walker’s perspective	poster (.pdf)
2009-04-06	The 12th Israeli Bioinformatics Symposium, Weizmann Institute of Science, Israel.	poster (.ppt)
2009-04-01	The 4th Stringology Research Workshop, Bar Ilan University, Israel.	talk (.ppt)
2009-03-30	FameLab Israel semifinals 2009, Hemda Science Education Centre, Tel Aviv, Israel.	transcript (.doc, hebrew)
2009-05-18 – 2009-05-21	13th Annual International Conference on Research in Computational Molecular Biology (RECOMB ’09), Tucson, Arizona, USA. Talk: Topology-free querying of protein interaction networks	talk (.ppt)
2008-06-02 – 2008-06-03	Edmond J. Safra Bioinformatics Program Retreat 2008, Achziv, Israel.

Publications

BibTeX bibliography data of my publications

Journal articles

• Sharon Bruckner, Falk Hüffner, and Christian Komusiewicz:
  A graph modification approach for finding core–periphery structures in protein interaction networks.
  Algorithms for Molecular Biology 10:16, 2015. [show abstract]

  Abstract. The core–periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core–periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

• Marco Sarich, Nataša Djurdjevac, Sharon Bruckner, Tim O. F. Conrad, and Christof Schütte:
  Modularity revisited: A novel dynamics-based concept for decomposing complex networks
  Journal of Computational Dynamics, 1(1):191–212, 2014 (original publication). [show abstract]

  Abstract. Finding modules (or clusters) in large, complex networks is a challenging task, in particular if one is not interested in a full decomposition of the whole network into modules. We consider modular networks that also contain nodes that do not belong to one of modules but to several or to none at all. A new method for analyzing such networks is presented. It is based on spectral analysis of random walks on modular networks. In contrast to other spectral clustering approaches, we use different transition rules of the random walk. This leads to much more prominent gaps in the spectrum of the adapted random walk and allows for easy identification of the network's modular structure, and also identifying the nodes belonging to these modules. We also give a characterization of that set of nodes that do not belong to any module, which we call transition region. Finally, by analyzing the transition region, we describe an algorithm that identifies so called hub-nodes inside the transition region that are important connections between modules or between a module and the rest of the network. The resulting algorithms scale linearly with network size (if the network connectivity is sparse) and thus can also be applied to very large networks.

• Nataša Djurdjevac, Sharon Bruckner, Tim O. F. Conrad, and Christof Schütte:
  Random walks on complex modular networks.
  Journal of Numerical Analysis, Industrial and Applied Mathematics, 6(1–2):29–50, 2011 (original publication). [show abstract]

  Abstract. Complex modular networks appear frequently, notably in the biological or social sciences. We focus on two current challenges regarding network modularity: the ability to identify (i) the modules of a given network, and (ii) the hub states as nodes with highest importance in terms of the communication between modules. Our approach towards these goals uses random walks as a mean to global analysis of the topology and communication structure of the network. We show how to adapt recent research regarding coarse graining of random walks. The resulting algorithms are based on spectral analysis of random walks and allow (A) an optimal identification of fuzzy assignments of nodes to modules, (B) computation of the fraction of the overall communication between modules supported by certain nodes, and (C) determination of the hubs as the nodes with the highest communication load.

• Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan:
  Topology-free querying of protein interaction networks.
  Journal of Computational Biology 17(3):237–252, 2010 (original publication). [show abstract]

  Abstract. In the network querying problem, one is given a protein complex or pathway of species A and a protein–protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query in terms of sequence, topology, or both. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To address this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while giving results that are highly functionally coherent.

• Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan:
  Torque: Topology-free querying of protein interaction networks.
  Nucleic Acids Research 37(Web Server issue):W106–W108, 2009 (original publication). [show abstract]

  Abstract. Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in one species, can a similar complex or pathway be found in the protein network of another species? To this end, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the target network, while allowing for both insertions and deletions. Unlike existing approaches, Torque does not require knowledge of the interconnections among the query proteins. It can handle large queries of up to 25 proteins.

Conference articles

• Sharon Bruckner, Falk Hüffner, and Christian Komusiewicz:
  A graph modification approach for finding core–periphery structures in protein interaction networks.
  In Proceedings of the 14th Workshop on Algorithms in Bioinformatics (WABI ’14), Wrocław, Poland. September 2014.
  Volume 8701 in Lecture Notes in Bioinformatics, pages 340–351, Springer, 2014 (original publication). Journal version available. [show abstract]

  Abstract. The core–periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core–periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

• Sharon Bruckner, Bastian Kayser, and Tim O. F. Conrad:
  Finding modules in networks with non-modular regions.
  In 12th International Symposium on Experimental Algorithms (SEA ’13), Rome, Italy. June 2013.
  Volume 7933 in Lecture Notes in Computer Science, pages 188–199, Springer, 2013 (original publication). [show abstract]

  Abstract. Most network clustering methods share the assumption that the network can be completely decomposed into modules, that is, every node belongs to (usually exactly one) module. Forcing this constraint can lead to misidentification of modules where none exist, while the true modules are drowned out in the noise, as has been observed e.g. for protein interaction networks. We thus propose a clustering model where networks contain both a modular region consisting of nodes that can be partitioned into modules, and a transition region containing nodes that lie between or outside modules. We propose two scores based on spectral properties to determine how well a network fits this model. We then evaluate three (partially adapted) clustering algorithms from the literature on random networks that fit our model, based on the scores and comparison to the ground truth. This allows to pinpoint the types of networks for which the different algorithms perform well.

• Sharon Bruckner, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier:
  Evaluation of ILP-based approaches for partitioning into colorful components.
  In 12th International Symposium on Experimental Algorithms (SEA ’13), Rome, Italy. June 2013.
  Volume 7933 in Lecture Notes in Computer Science, pages 176–187, Springer, 2013 (original publication). [show abstract]

  Abstract. The NP-hard Colorful Components problem is a graph partitioning problem on vertex-colored graphs. We identify a new application of Colorful Components in the correction of Wikipedia interlanguage links. We then describe and compare several exact and heuristic approaches for solving Colorful Components. In particular, we devise two ILP formulations, where one employs a relationship to the Hitting Set problem and the other one uses a Clique Partition formulation. Furthermore, we use the recently proposed implicit hitting set framework [Karp, JCSS 2011, Chandrasekaran et al., SODA 2011] to solve Colorful Components. Finally, we also study a move-based and a merge-based heuristic for Colorful Components. Our approach can solve the Colorful Components model of Wikipedia link correction optimally; while the Clique Partition-based ILP outperforms the other two approaches, the implicit hitting set is a simple approach that delivers competitive results. Finally, the merge-based heuristic is very accurate and outperforms the move-based one.

• Sharon Bruckner, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Sven Thiel, and Johannes Uhlmann:
  Partitioning into colorful components by minimum edge deletions.
  In Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM ’12), Helsinki, Finland. July 2012.
  Volume 7354 in Lecture Notes in Computer Science, pages 56–69, Springer, 2012 (original publication). [show abstract]

  Abstract. The NP-hard Colorful Components problem is, given a vertex-colored graph, to delete a minimum number of edges such that no connected component contains two vertices of the same color. It has applications in multiple sequence alignment and in multiple network alignment where the colors correspond to species. We initiate a systematic complexity-theoretic study of Colorful Components by presenting NP-hardness as well as fixed-parameter tractability results for different variants of Colorful Components. We also perform experiments with our algorithms and additionally develop an efficient and very accurate heuristic algorithm clearly outperforming a previous min-cut-based heuristic on multiple sequence alignment data.

• Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan:
  Topology-free querying of protein interaction networks.
  In Proceedings of the 13th Annual International Conference on Research in Computational Molecular Biology (RECOMB ’09), Tucson, Arizona, USA. May 2009.
  Volume 5541 in Lecture Notes in Bioinformatics, pages 74–89, Springer (original publication). [show abstract]

  Abstract. In the network querying problem, one is given a protein complex or pathway of species A and a protein-protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To combat this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while in both cases giving results that are highly functionally coherent.

Posters

• Sharon Bruckner, Tim O. F. Conrad, and Christof Schütte:
  Understanding biological networks with the random walker’s perspective.
  Presented at the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB ’11).
  Also at F1000 Posters 2011, 2:392. [show abstract]

  Abstract. We present a new method for analyzing networks and demonstrate its applications to biological networks. The networks we study are modular, meaning that they display a structure of dense communities connected by sparser formations. It has been observed that biological networks, such as protein-protein interaction networks, often exhibit this structure [Girvan and Newman 2002]. We propose an approach to reveal the organization of such networks. Unlike previous methods, that aim to identify a specific type of network element (community detection, hubs identification, etc.), our methods discover these individual elements as well as the connections between them: finding modules, identifying the important paths between them, and most importantly pinpointing the key nodes in the network, those that are the most vital to communication between the modules. Such nodes could, for example, be good candidates for drug targets. We base our novel algorithms on the random walker approach to modular networks. Here the modules correspond to metastable sets: regions of the network where a random walker stays for a long time before exiting. We then associate the important paths and key nodes with those carrying the most flow in the sense of transition path theory [Metzner et al. 2009], a rigorous framework with proven properties originally designed for the study of dynamical systems.

Theses

• Sharon Bruckner:
  Modularity in Biological Networks.
  PhD thesis, Freie Universität Berlin, 2014. [show abstract]

  Abstract. Networks are commonly used to model complex real-world systems such as the cell or the brain. An important notion in analyzing networks is modularity. Usually, a network is considered modular if all its nodes can be partitioned into dense, connected subsets that are sparsely connected to one another. In this thesis, we extend the definition of modularity to cover networks that do contain dense modules that are sparsely connected to the rest of the network, but some nodes can belong to the region outside of modules, the so-called transition region. Accordingly, in contrast to full partitions, this work deals considers assignments: The association of every node to a module in the modular region or to the transition region.
  The first task to be tackled in this thesis is the construction of a formal definition of modularity. After surveying some of the prominent existing definitions in the literature, we found that they cannot be directly applied to networks that are not fully-partitionable. We then developed an approach based on time-continuous random walks for analyzing networks. Here we built on a rich literature on the topic of spectral clustering, equating network modules with metastable sets of a random walk. This allows us to define a network as modular if there is a choice of modules that produces a coarse-grained Markov process whose dynamics well-approximate those of the original random walk on the network. We first demonstrate that this score matches our intuition of modularity on synthetic networks, increasing with the density of the modules and in the case where the modular region is large. Perturbation analysis is then used to formally prove the correct behavior of the score on two specifically constructed classes of networks.
  Motivated both by the need to provide a good assignment as input to the modularity score and by the established usefulness of clustering methods, the second task to be tackled is that of finding good assignments. Continuing with the approach of Markov models, we first describe an algorithm based on a continuous random walk on the network. Next, modifications to several leading full-partition algorithms are described so that they output modules and transition regions rather than full partitions. The performance of all algorithms is then tested on a class of benchmark networks. Finally, we developed a combinatorial model of networks that are not fully partitionable as a union of split graphs, and posed the problem of finding modules and transition regions as a graph editing problem, proving its hardness and providing exact algorithms and heuristics.
  The discussion of each of the two tasks is completed by an example of a biological application. Identifying good assignments gives us a way to detect protein complexes in protein interaction networks, a well-studied topic. The flexibility of assigning proteins to modules or to the transition region helps identify more complicated structures as complexes. The modularity score is used to analyze the brain networks of autistic and typically-developed children, where the distribution of modularity scores is different between the two types. In future work it will be interesting to further investigate the modularity of biological networks and draw conclusions about their organization.

• Sharon Bruckner:
  Topology-Free Querying of Protein Interaction Networks.
  Master's thesis, School of Computer Science, Tel Aviv University, 2009. [show abstract]

  Abstract. In the network querying problem, one is given a protein complex or pathway of species Α and a protein–protein interaction network of species Β; the goal is to identify subnetworks of Β that are similar to the query in terms of sequence, topology, or both. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species Α; however, in practice, this topology is often not known. To address this problem, we developed a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming, integer linear programming, and fast heuristics. We tested Torque with queries from yeast, fly, and human, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than previous approaches, while giving results that are highly functionally coherent. Our implementation is available to the public via a web interface.

Software

• Web server for Torque (Topology-Free Querying of Protein Interaction Networks)
  

  Given a complex (set of proteins) for a query species, Torque seeks a matching set of proteins of a target species that are sequence-similar to the query proteins and span a connected region of the target network. It allows both deletions (query proteins that have no match in the output) and insertions (proteins in the output that do not match any query input and are inserted to keep the output connected).