Personal

Contacts: www.dvorkin.me

E-mail: mikhail.dvorkin@gmail.com

Scientific Interests

Algorithm and Data Structures, Complexity Theory, Computational Genomics and Proteomics

• Automatized proof of NP-complexity of 2D locally-dependant problems (in Russian)
• NP-completeness of n-CROSS SUM for n=4,5,6
• I. R. Akishev, M. E. Dvorkin, Minimum DFA recognizing a prefix-code of given cardinality (in Russian)

Career

Academic University Algorithmic Biology Lab, researcher (2011—present)

Lyceum "Physical-Technical High School", computer science and math teacher (2008—present)

St. Petersburg State University of Information Technologies, Mechanics and Optics (2006—present)

Experience

Summer Informatics School, teacher and entertainment deputy director (2006—present)

Russian Olympiad in Informatics, science committee member (2005—2008)

ACM ICPC NEERC, technical committee member (2007—present)

Education

B. Sc., M. Sc, Ph. D. student in Math and Computer Science, St. Petersburg State University of Information Technologies, Mechanics and Optics, St. Petersburg, Russia (2004—present)

Russian Mission to the UN High School, New York, NY (2004)

Stuyvesant High School, New York, NY (2001—2004)

Lyceum "Physical-Technical High School", St. Petersburg, Russia (1999—2003)

School 582, St. Petersburg, Russia (1994—1999)

Awards

ACM ICPC World Finals, Gold Medal (2007)

ACM ICPC NEERC, Vice-champion (2005, 2006)

TopCoder Open, 8th place (2007)

International Problem Solving Contest, Champion (2007)

Test The Best, Champion (2007)

Russian Olympiad in Informatics, High School, Vice-champion (2003)

Education:

• 2009 - current: PhD student, St. Petersburg State University, Mathematical & Mechanics Faculty, Department of Computer Science.
• 2003 - 2009: St. Petersburg State University, Mathematics & Mechanics Faculty, Department of Algebra (diploma thesis: "Reducibility for disjoint NP-pairs with advice").

Awards:

• 2010 - sllver medal on ACM ICPC World Finals.
• 2009, 2004 - 6th place on NorthEastern European Regional Contest.
• 2004, 2005, 2009 - SPbSU programming contests champion.

Experience:

• 2008: junior software engineer (intern), JetBrains.
• 2009 - 2010: junior software engineer (intern) Yandex.
• 2010 - 2011: (junior) software engineer, Vkontakte.

Scientific interests:

• structural complexity theory,
• effective algorithms,
• paired de Bruijn graphs,
• genome assemblers.

EDUCATION:

• Ph. D. student Computer Science (Applied Math) St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, St. Petersburg, Russia now (Dec., 2005 – Dec., 2008)
• M.Sc. Mathematics Mathematics and Mechanics Department of St. Petersburg State University, St. Petersburg, Russia 2005 (Sept., 2000–Jul., 2005)

RESEARCHE INTERESTS:

• Bayesian inference:
  • Bayesian networks.
  • Rating systems.
• Computational Genomics and Proteomics:
  • Paired de Bruijn graphs in genome assembling.

MAIN PUBLICATIONS:

1. A. L. Tulupyev, S. I. Nikolenko, A. V. Sirotkin. Bayesian Networks: A Probabilistic Logic Approach. St.-Petersburg, Nauka, 2006. 608 p (in Russian)
2. A. L. Tulupyev, A. V. Sirotkin, S. I. Nikolenko  Bayesian belief networks: probabilistic logic inference in acyclic directed graphs. St.-Petersburg, St.-Petersburg state university press, 2009. 400 p. (in Russian)
3. S.I. Nikolenko, A.V. Sirotkin. Worst-case upper bounds for SAT: automated proof. Student Session Proceedings, 15th European Summer School in Logic, Language, and Information (ESSLLI 2003). Vienna, Austria, 2003. P. 225–232.
4. Sergey I. Nikolenko, Alexander Sirotkin Extensions of the Trueskill™ Rating System // Proceedings of Ninth International Conference on Application of Fuzzy Systems and Soft Computing, Prague, Czech Republic August 26-27, 2010, pp. 156-165.
5. S.I. Nikolenko, A.V. Sirotkin. A New Bayesian Rating System for Team Competitions. To appear in Proceedings of the 28th International Conference on Machine Learning (ICML 2011), 2011.

EXTRACURRICULAR:

• Participant of the 15th European Summer School in language, logic and information (ESSLLI 2003), held in Vienna, Austria. August 2003
• Participant of the IV International Seminar “Integrated models and soft computing in artificial intelligence”, Kolomna, Russia. May 2007
• Participant of the V International Seminar “Integrated models and soft computing in artificial intelligence”, Kolomna, Russia. May 2009
• Organizer of the International Seminar for junior scientists, Kolomna, Russia. May 2009

Hello, dear guest.

My name is Sergey Nurk and I live in Saint-Petersburg, Russia.

In 2011 I graduated with honors from SPbSU Department of Software Engineering

This page is no longer maintained (after the transfer of the lab to a different university).

Up to date personal page can be found here.

Publications (until 2015):

1. Sergey Nurk, Pavel A. Pevzner

“SPArcle: Identifying Microbial Genome Variations with Colored de Bruijn Graphs”.

Manuscript in preparation

2. Yu Lin, Sergey Nurk and Pavel A. Pevzner

“What is the difference between the breakpoint graph and the de Bruijn graph? ”.

S6 BMC Genomics Volume 15 Supplement 6, 2014: Proceedings of the Twelfth Annual Research in Computational Molecular Biology (RECOMB) Satellite Workshop on Comparative Genomics.

3. Gabriela I Guzman, Jose Utrilla, Sergey Nurk, Elizabeth Brunk, Jonathan M Monk, Ali Ebrahim, Bernhard Ø Palsson, Adam M. Feist

“Model-driven discovery of underground metabolic functions in Escherichia coli”.

Accepted to PNAS

4. Andrey D. Prjibelski, Irina Vasilinetc, Anton Bankevich, Alexey Gurevich, Tatiana Krivosheeva, Sergey Nurk, Son Pham, Anton Korobeynikov, Alla Lapidus and Pavel A. Pevzner

“ExSPAnder: a universal repeat resolver for DNA fragment assembly”.

Bioinformatics, 30(12), i293-i301, 2014

5. Sergey Nurk, Anton Bankevich ( equal contribution), Dmitry Antipov, Alexey A. Gurevich, Anton Korobeynikov, Alla Lapidus, Andrey D. Prjibelski, Alexey Pyshkin, Alexander Sirotkin, Yakov Sirotkin, Ramunas Stepanauskas, Scott R. Clingenpeel, Tanja Woyke, Jeffrey S. Mclean, Roger Lasken, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner

“Assembling Single-Cell Genomes and Mini-Metagenomes From Chimeric MDA Products”.

Journal of Computational Biology 20(10), 2013

6. Sergey Nurk, Anton Bankevich ( equal contribution), Dmitry Antipov, Alexey A. Gurevich, Anton Korobeynikov, Alla Lapidus, Andrey Prjibelsky, Alexey Pyshkin, Alexander Sirotkin, Yakov Sirotkin, Ramunas Stepanauskas, Jeffrey McLean, Roger Lasken, Scott R. Clingenpeel, Tanja Woyke, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner

“Assembling Genomes and Mini-metagenomes from Highly Chimeric Reads”.

Proceedings of the 17th Annual International Conference on Research in Computational Molecular Biology, Lecture Notes in Computer Science 7821 (2013).

7. Jeffrey S. McLean, Mary-Jane Lombardo, Michael G. Ziegler, Mark Novotny, Joyclyn Yee-Greenbaum, Jonathan H. Badger, Glenn Tesler, Sergey Nurk, Valery Lesin, Daniel Brami, Adam P. Hall, Anna Edlund, Lisa Z. Allen, Scott Durkin, Sharon Reed, Francesca Torriani, Kenneth H. Nealson, Pavel A. Pevzner, Robert Friedman, J. Craig Venter and Roger S. Lasken

“Genome of the pathogen Porphyromonas gingivalis recovered from a biofilm in a hospital sink using a high-throughput single cell genomic platform”.

Genome research, 23(5), 867-877

8. Anton Bankevich, Sergey Nurk ( equal contribution), Dmitry Antipov, Alexey Gurevich, Mikhail Dvorkin, Alexander Kulikov, Valery Lesin, Sergey Nikolenko, Son Pham, Andrey Prjibelski, Alexey Pyshkin, Alexander Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max Alekseyev and Pavel Pevzner

“SPAdes: a New Genome Assembler and its Applications to Single Cell Sequencing”.

Journal of Computational Biology 19(5), 2012

9. Sergey Nurk

“An Upper Bound for Circuit SAT”.

PDMI preprint 10/2009, 2009 

Education:

• 2003-2007 Conducted classes in Olympiad Mathematics for school students at specialized school #533, St. Petersburg.
• 2008, 2010 Conducted classes in Mathematics for students at St. Petersburg State University.

• Yana Safonova, Anton Bankevich, Pavel A. Pevzner ”DipSPAdes: Assembler for Highly Polymorphic Diploid Genomes” RECOMB2014.
• Sergey Nurk, Anton Bankevich, Dmitry Antipov, Alexey Gurevich, Anton Korobeynikov, Alla Lapidus, Andrey Prjibelsky, Alexey Pyshkin, Alexander Sirotkin, Yakov Sirotkin, Ramunas Stepanauskas, Jeffrey McLean, Roger Lasken, Scott R. Clingenpeel, Tanja Woyke, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner:  “Assembling Genomes and Mini-metagenomes from Highly Chimeric Reads.”  Journal of Computational Biology 20(10), 2013
• Sergey Nurk, Anton Bankevich, Dmitry Antipov, Alexey Gurevich, Anton Korobeynikov, Alla Lapidus, Andrey Prjibelsky, Alexey Pyshkin, Alexander Sirotkin, Yakov Sirotkin, Ramunas Stepanauskas, Jeffrey McLean, Roger Lasken, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner “Assembling Genomes and Mini-metagenomes from Highly Chimeric Reads.” RECOMB2013, Beijing, China.
• Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey Gurevich, Mikhail Dvorkin, Alexander Kulikov, Valery Lesin, Sergey Nikolenko, Son Pham, Andrey Prjibelski, Alexey Pyshkin, Alexander Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max Alekseyev and Pavel Pevzner “SPAdes: a New Genome Assembler and its Applications to Single Cell Sequencing.” Journal of Computational Biology 19(5). 2012.
• A. V. Bankevich “Bounds of the number of leaves of spanning trees in graphs without triangles” Journal of Mathematical Sciences, August 2012, Volume 184, Issue 5, pp 557-563.
• A. V. Bankevich, D. V. Karpov “Bounds of the number of leaves of spanning trees” Journal of Mathematical Sciences, August 2012, Volume 184, Issue 5, pp 564-572.

• 2004 the second award on All-Russian Math Olympiad.
• 2008 the second award on ACM North-Eastern region semifinal.

Начало семинаров — 4 июля 2011 (понедельник).

Подробное расписание опубликовано здесь.

Материалы лекций:

• 05/07/2011: Intro to computational MS (Pavel) — slides (pptx)
• 06/07/2011: Spectral probabilities and spectral dictionaries (Pavel) — slides (ppt)
• 07/07/2011: Target-Decoy Search in MS: When things may go wrong (Kira) — slides (pdf), paper: Target-Decoy Approach and False Discovery Rate: When Things May Go Wrong (Gupta et al., 2011) (including supplement)
• 08/07/2011: Deconvolution and Database Search of Complex Top-Down Tandem Mass Spectra — slides (ppt), paper: Protein Identification Using Top-Down Spectra (Liu et al. 2011) (including supplement)
• 11/07/2011:  Block Pattern Matching and its Applications in Proteomics (Kira) — slides (ppt), paper: Blocked Pattern Matching Problem and its Applications in Proteomics (Ng et al., 2011)
• 12 12/07/2011: Gapped Spectral Dictionaries (Max Gladkih) — slides (odp), paper: Gapped spectral dictionaries and their applications for database searches of tandem mass spectra (Jeong et al. 2011) http://www.ncbi.nlm.nih.gov/pubmed/21444829
• 26/07/2011: TBA (Alexey Nezhvinsky, University of Michigan) — slides (TBA), paper (TBA).
• 27/07/2011: De Novo peptide sequencing (Sergey Nikolenko) — slides (pdf), papers: De novo peptide sequencing via tandem mass spectrometry (Dancik et al. 1999), A ranking-based scoring function for peptide-spectrum matches (Frank. 2009).

Освещаемые статьи:

• Imaging mass spectrometry of intraspecies metabolic exchange revealed the cannibalistic factors of Bacillus subtilis. Liu et al. 2010.
• Blocked Pattern Matching Problem and its Applications in Proteomics. Ng et al., 2011
• Spectral Profiles, a Novel Representation of Tandem Mass Spectra and Their Applicationsfor de Novo Peptide Sequencing andIdentification. Kim et al. 2009.
• Spectral dictionaries: Integrating de novo peptide sequencing with database search of tandem mass spectra. Kim et al. 2009.
• Spectral probabilities and generating functions of tandem mass spectra: a strike against decoy databases. Kim et al. 2008.
• Shotgun protein sequencing: assembly of peptide tandem mass spectra from mixtures of modified proteins. Bandeira et al. 2007.
• Protein identification by spectral networks analysis. Bandeira et al. 2007.
• Identification of post-translational modifications by blind search of mass spectra. Tsur et al. 2005. http://www.ncbi.nlm.nih.gov/pubmed/16311586
• InsPecT: identification of posttranslationally modified peptides from tandem mass spectra. Tanner et al. 2005.
• De novo peptide sequencing via tandem mass spectrometry. Dancik et al. 1999.
• A ranking-based scoring function for peptide-spectrum matches. Frank. 2009.