Sharon Bruckner

Sharon Bruckner (Hüffner)

I am a PhD Student 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.

I am interested in network analysis and graph algorithms. My current project is fuzzy clustering of networks using spectral analysis, with applications in bioinformatics.

Address:
Sharon Bruckner
Freie Universität Berlin
Department of Mathematics and Computer Science
Mathematics Institute
Biocomputing Group
Arnimallee 6 — Room 115
14195 Berlin

Phone: +49 30 838 75334
Fax: +49 30 838 75412

Email:

Where I have been in former times

• 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

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

• Marco Sarich, Nataša Djurdjevac, Sharon Bruckner, Tim O. F. Conrad, and Christof Schütte:
  Use multilevel random walks to find modules and hubs in complex networks.
  Manuscript, submitted, 2012.
• 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, 2011 (in press). [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, 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.
  Lecture Notes in Computer Science, Springer (to appear). [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.

Thesis

• 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).