Dina Sokol
Professor
Computer and Information Science
Location: 3209d Ingersoll Hall
Phone: 718.951.5000 x2065
Fax: 718.951.4842
Email:
Dina Sokol's Web site
Dina Sokol is a full professor in the Department of Computer and Information Science at Brooklyn College and the Graduate Center of the City University of New York. She completed her Ph.D. and postdoctoral studies in Computer Science at Bar-Ilan University in 2003.
Sokol's research area is in the field of combinatorial pattern matching, a subarea of the field of algorithm design and analysis. Funded by the NSF, Sokol's research group has developed software for locating tandem repeats in DNA, and a database of tandem repeats in the human genome called TredD. Sokol publishes in both theoretical journals such as TCS, and bioinformatics journals, and she has been a member of the program committees for several pattern matching conferences. She supervises undergraduate students, Master's students and Ph.D. students.
Education:
Ph.D., Bar Ilan University (Israel) - 2003 (Computer Science)
M.Sc., Polytechnic University - 1998 (Computer Science)
M.A., Brooklyn College - 1996 (Computer and Information Science)
B.S., Thomas Edison State College - 1995 (Computer Science)
Areas of Expertise:
Design and analysis of string algorithms. Specific areas of interest include: matching in compressed inputs, parameterized matching, two-dimensional pattern matching, and detecting repetitive sequences in strings.
Books and Publications
A. Amir, A. Butman, E. Kondratovsky, A. Levy and D. Sokol. Multidimensional Period Recovery. Algorithmica (2022). https://doi.org/10.1007/s00453-022-00926-y (Books and Publications: Article (Peer-reviewed)) 2022
Amihood Amir, Ayelet Butman, Eitan Kondratovsky, Avivit Levy and Dina Sokol. Multidimensional Period Recovery. 27th International Symposium on String Processing and Information Retrieval. (Books and Publications: Article (Peer-reviewed)) 2020
Amihood Amir, Gad M. Landau, Shoshana Marcus, Dina Sokol. Two-dimensional maximal repetitions. Theoretical Computer Science 812: 49-61 (2020) (Books and Publications: Article (Peer-reviewed)) 2020
Dina Sokol. 2-Dimensional Palindromes with k Mismatches. Information Processing Letters (2020) https://doi.org/10.1016/j.ipl.2020.106019 (Books and Publications: Article (Peer-reviewed)) 2020
Double String Tandem Repeats, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, 3:1-3:13 https://doi.org/10.4230/LIPIcs.CPM.2020.3 (Books and Publications: Article (Peer-reviewed)) 2020
Efficient Algorithms for Finding Exact and Approximate 2D Side-Sharing Tandems. Masters Thesis of Tova Neuburger. (Books and Publications: Other) 2020
S. H. Geizhals and D. Sokol. Finding maximal 2-dimensional palindromes. Information and Computation, 266, 161-172, 2019. https://doi.org/10.1016/j.ic.2019.03.001 (Books and Publications: Article (Peer-reviewed)) 2019
Period Recovery of Strings over the Hamming and Edit Distances.
Amihood Amir, Mika Amit, Gad M. Landau, and Dina Sokol. Theoretical Computer Science, (710), 2-18, 2018. (Books and Publications: Article (Peer-reviewed)) 2018
Locating All Approximate Runs in a String.
Mika Amit, Maxime Crochemore, Gad M. Landau, Dina Sokol. Theoretical Computer Science (700), 45-62, 2017. . (Books and Publications: Article (Peer-reviewed)) 2017
S. Marcus and D. Sokol. 2D Lyndon Words and Applications. Algorithmica, 77 (1), 116-133, 2017. (Books and Publications: Article (Peer-reviewed)) 2017
A. Amir, M. Amit, G. M. Landau and D. Sokol. Period Recovery over the Hamming and Edit Distances. In Proceedings of the Latin American Theoretical Informatics Symposium, LATIN 2016. (Books and Publications: Article (Peer-reviewed)) 2016
S. H. Geizhals and D. Sokol. 2D Palindromes. In Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. (Books and Publications: Article (Peer-reviewed)) 2016
Advances in Stringology. Volume 525 of the journal Theoretical Computer Science. March 13. (Books and Publications: Book (Edited)) 2014
Sokol, D. and J. Tojeira. "Speeding Up the Detection of Tandem Repeats Over the Edit Distance." Theoretical Computer Science 525: 103-10. http://dx.doi.org/10.1016/j.tcs.2013.04.021. (Books and Publications: Article (Peer-reviewed)) 2014
Liang, Y., D. Sokol, S. Zelikovitz and S.I. Levitan. "Classification of Tandem Repeats in the Human Genome." International Journal of Knowledge Discovery in Bioinformatics 3.3: 1-21. (Books and Publications: Article (Peer-reviewed)) 2013
Marcus, S. and D. Sokol. "Engineering Small Space Dictionary Matching." arXiv preprint arXiv:1301.6428. (Books and Publications: Article (Other)) 2013
Marcus, S. and D. Sokol. "Engineering Small Space Dictionary Matching." Submitted to Symposium on Experimental Algorithms, SEA. (Books and Publications: Forthcoming Publications) 2013
Marcus, S. and D. Sokol. "On 2-dimensional Lyndon Words." Proceedings of the 20th International Symposium on String Processing and Information Retrieval, Jerusalem, Israel, October 2013. 206-17. (Books and Publications: Article (Peer-reviewed)) 2013
Neuburger, S. and D. Sokol. "Succinct 2D Dictionary Matching." Algorithmica 65.3: 662-84. DOI: 10.1007/s00453-012-9615-9. (Books and Publications: Article (Peer-reviewed)) 2013
Liang, Y., D. Sokol and S. Zelikovitz. "Clustering Tandem Repeats via Trinucleotides." Proceedings of IEEE International Conference on Data Mining, Workshop on Biological Data Mining. IEEE Computer Society. 64-71. (Books and Publications: Article (Peer-reviewed)) 2012
S. Neuburger and D. Sokol. "Succinct 2D Dictionary Matching with No Slowdown." Proceedings of the 18th International Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, Springer-Verlag. 619-30. (Books and Publications: Article (Peer-reviewed)) 2011
Sokol, D. and F. Atagun. "TRedD: A Database for Tandem Repeats Over the Edit Distance." Database (2010); 2010: article ID baq003, 10.1093/database/baq003. (Books and Publications: Article (Peer-reviewed)) 2010
Sokol, Dina, Frederick Adkins, Zhongyuan Che and Kristin Pfabe. "Finding Repeats Within Strings." DIMACS Educational Module Series, 09-2. Available at http://dimacs.rutgers.edu/Publications/Modules/Module09-2/dimacs09-2.pdf. (Books and Publications: Article (Peer-reviewed)) 2009
Kucherov, Gregory and Dina Sokol. "Approximate Tandem Repeats." Encyclopedia of Algorithms. Springer. (Books and Publications: Book Chapter) 2008
Amir, A., G.M. Landau, M. Lewenstein and D. Sokol. "Dynamic Text and Static Pattern Matching." ACM Transactions on Algorithms 3.2. (Books and Publications: Article (Peer-reviewed)) 2007
Harel, C., M. Lewenstein and D. Sokol. "Approximate Parameterized Matching." ACM Transactions on Algorithms 3.3. (Books and Publications: Article (Peer-reviewed)) 2007
Sokol, D., G. Benson and J. Tojeira. "Tandem Repeats Over the Edit Distance." Bioinformatics 23.2: e30-35. (Books and Publications: Article (Peer-reviewed)) 2007
Amir, A., G.M. Landau and D. Sokol. "Inplace 2D Matching in Compressed Images." Journal of Algorithms 49.2: 240-61. (Books and Publications: Article (Peer-reviewed)) 2003
Amir, A., G.M. Landau and D. Sokol. "Inplace Run-length 2-dimensional Compressed Search." Theoretical Computer Science 290.3: 1361-83. (Books and Publications: Article (Peer-reviewed)) 2003
Landau, G.M., J.P. Schmidt and D. Sokol. "An Algorithm for Approximate Tandem Repeats." Journal of Computational Biology 8.1: 1-18. (Books and Publications: Article (Peer-reviewed)) 2001
Creative Work
Marcus, Shoshana and Dina Sokol. Software for Small Space Dictionary Matching. Available open source at http://www.sci.brooklyn.cuny.edu/~sokol/dictmatch.html. 2013
Software and Website Development: TRedD - Tandem Repeats over the edit Distance Database. Developed open source software for locating tandem repeats, TRed, and a database of tandem repeats in the human genome, TRedD, available at: http://tandem.sci.brooklyn.cuny.edu. 2009
TandemGraph: Designed, developed and maintain software for graphically depicting the tandem repeats that occur in a chromosome. 2009
Software and Website Development: Smith-Waterman Repeat Finder. Developed a Java program for finding general repeats within a sequence based on the Smith-Waterman algorithm for local sequence alignment. Developed an online interface for running the program. 2008
Awards, Honors and Fellowships
Recovery in Strings. US-Israel Binational Science Foundation. $129,000 2019-2022 (Grants and Fellowships) 2019-2022 (Grants and Fellowships) 2019
Approximate Cycles and Repetitions. US-Israel Binational Science Foundation. $129,000 2016-2019 (Grants and Fellowships) 2016
PSC-CUNY 44 Research Award Program TRADB-44-88, for "Speeding Up Tandem Repeat Detection." $5,044; July 1, 2013 - June 30, 2014. (Grants and Fellowships) 2013
PSC-CUNY Research Award Program 43, for "Small-space Dictionary Matching Software." $3,496. (Grants and Fellowships) 2013
"Issues in Combinatorial Pattern Matching - Approximate Cycles and Repeats," submitted to BSF US-Israel Binational Science Foundation. Requested amount: $198,605. (Grants and Fellowships) 2012
NSF Computer and Communication Foundations, Program Algorithmic Foundations, submitted for "Dictionary Matching in Small Space." Requested amount: $396,334. (Grants and Fellowships) 2010
NSF Division of Biological Infrastructure, Program Advances in Biological Informatics, submitted for "Clustering and Visualizing Tandem Repeats." Requested amount: $378,759. (Grants and Fellowships) 2010
PSC-CUNY Research Award Program 41, Award # 63343-00 41, for "Small Space Dictionary Matching." $2,860. (Grants and Fellowships) 2010
PSC-CUNY Research Award # 62280-00 40, for "TandemGraph: A Graphical Tool for Modeling String Regularities." $4,298. (Grants and Fellowships) 2009
PSC-CUNY 38 Research Award Program, #69273-0038, for "TRED: A GUI Interface for Finding Tandem Repeats Over the Edit Distance." D. Sokol, S. Singh and S. Zelikovitz, co-recipients. $4,090. (Grants and Fellowships) 2008
CRA-W Computing Research Association Distributed Mentors Program. D. Sokol and N. Gurwitz, co-recipients. $8,500; July 1-Aug. 30. (Grants and Fellowships) 2006
NSF Division of Biological Infrastructure, Biological Databases and Informatics Program, for "Approximate Tandem Repeats Database, DBI-0542751." $321,308; Sept. 1, 2006-Aug. 31, 2009. (Grants and Fellowships) 2006
PSC-CUNY 37 Research Award Program, #68799-0037, for "Approximate Tandem Repeats." $3,175; Aug. 1, 2006-July 30, 2007. (Grants and Fellowships) 2006
PSC-CUNY 36 Research Award Program, #67217-0036, for "Approximate Tandem Repeats." $3,612.26; Aug. 1, 2005-July 30, 2006. (Grants and Fellowships) 2005
Israel Science Foundation Fellowship, 2002-03. (Grants and Fellowships) 2002
KITE Grant of the Israel Ministry of Trade and Industry, 2000-01. (Grants and Fellowships) 2000
National Science Foundation Fellowship, Polytechnic University, 1997-98. (Grants and Fellowships) 1997
Jack Wolfe Fellowship, Brooklyn College. (Grants and Fellowships) 1996
Research Activities
https://github.com/mary060196/CISC5001_Research_Project_Implementing_TRed_Efficiently 2020
Ph.D. student Yupu Liang completed her thesis defense. Thesis title: "Analysis of DNA Motifs in the Human Genome." 2013
Undergraduate research: Mentored Ari Mermelstein in developing a parallel program to run on a massively parallel architecture for TRed -- finding repeats within biological sequences. 2013
Ph.D. student Shoshana Neuburger graduated. Thesis title: "Small Space 2-dimensional Dictionary Matching." 2012
Undergraduate research: Mentored an undergraduate student, P. Krauss. Developed an online interface with flexible parameter setting for the TRed program. 2012
Undergraduate research: Mentored S.I. Levitan in fall 2012. Project resulted in a classification method for the tandem repeats in the human genome based upon the trinucleotide frequencies in each repeat. 2012
Mentored a master's student in developing software for suffix tree construction. Developed software in Java for constructing a suffix tree and a generalized suffix tree for dictionary matching based on Ukkonen's algorithm. 2010
Conferences, Seminars and Symposiums
A. Amir, M. Amit, G. M. Landau and D. Sokol. Period Recovery over the Hamming and Edit Distances. Accepted at Latin American Theoretical Informatics Symposium, LATIN 2016. (Conferences, Seminars and Symposiums: Conference Presentation) 2016
S. Geizhals and D. Sokol. 2D Palindromes. Presented at the 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. (Conferences, Seminars and Symposiums: Conference Presentation) 2016
"On 2-dimensional Lyndon Words." SPIRE 2013 -- 20th International Symposium on String Processing and Information Retrieval. Jerusalem, Oct. 8. (Conferences, Seminars and Symposiums: Conference Presentation) 2013
"Small Space Dictionary Matching." Research at CUNY. CUNY Graduate Center. New York. (Conferences, Seminars and Symposiums: Invited Talk) 2011
Neuburger, S. and D. Sokol. "Succinct 2D Dictionary Matching With No Slowdown." Algorithms and Data Structures Symposium. New York. (Conferences, Seminars and Symposiums: Conference Presentation) 2011
Neuburger, S. and D. Sokol. "Small-space 2D Dictionary Matching." Combinatorial Pattern Matching Proceedings, 21st Annual Symposium, CPM 2010, New York. Lecture Notes in Computer Science 6129. Springer. 27-39. (Conferences, Seminars and Symposiums: Conference Presentation) 2010
"TRedD: A Database for Tandem Repeats Over the Edit Distance." Computer Science Departmental Colloquium. CUNY Graduate Center. New York, October. (Conferences, Seminars and Symposiums: Invited Talk) 2009
Sokol, D. and R. Rakhamimov. "TandemGraph: A Graphical Tool for Modeling String Regularities." Proceedings of BIOCOMP '09: International Conference on Bioinformatics & Computational Biology, Las Vegas. 536-40. (Conferences, Seminars and Symposiums: Conference Presentation) 2009
"TRED: Tandem Repeats Over the Edit Distance." The SCORE Retreat of Brooklyn College. New York Academy of Sciences. January. (Conferences, Seminars and Symposiums: Contributed Talk) 2007
Sokol, D., G. Benson and J. Tojeira. "Tandem Repeats Over the Edit Distance." European Conference of Computational Biology. January. (Conferences, Seminars and Symposiums: Conference Presentation) 2007
"Tandem Repeats Over the Edit Distance." Third Annual International Stringology Research Workshop. University of Haifa, Israel, May. (Conferences, Seminars and Symposiums: Invited Talk) 2006
Sokol, D. and J. Tojeira. "Filtering Tandem Repeats in DNA Sequences." Proceedings of BIOCOMP '06: International Conference on Bioinformatics & Computational Biology, Las Vegas.: 161-67. (Conferences, Seminars and Symposiums: Conference Presentation) 2006
Harel, C., M. Lewenstein and D. Sokol. "Approximate Parameterized Matching." Proceedings of the 12th Annual European Symposium on Algorithms: Lecture Notes in Computer Science 3221: 414-25. (Conferences, Seminars and Symposiums: Conference Presentation) 2004
Amir, A., G.M. Landau and D. Sokol. "2-D Matching in Compressed Images." Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms: 853-62. (Conferences, Seminars and Symposiums: Conference Presentation) 2003
Amir, A., G.M. Landau, M. Lewenstein and D. Sokol. "Dynamic Text and Static Pattern Matching." Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS): Lecture Notes in Computer Science 2748. Springer-Verlag. 340-64. (Conferences, Seminars and Symposiums: Conference Presentation) 2003
Amir, A., G.M. Landau and D. Sokol. "Inplace Run-length 2-dimensional Compressed Search." Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms: 817-18. (Conferences, Seminars and Symposiums: Conference Presentation) 2000
Professional Leadership
member of appointments committee (Professional Leadership: Committee Service) 2015
Faculty adviser to WICS (Women in Computer Science) student club. (Professional Leadership: Organizational Leadership Position) 2013
Member, Appointments Committee. (Professional Leadership: Committee Service) 2013
Chair, Undergraduate Curriculum Committee. (Professional Leadership: Committee Service) 2011
Member, Program Committee for SPIRE'11 - 18th Annual Symposium on String Processing and Information Retrieval. (Professional Leadership: Organizational Leadership Position) 2011
Composed a set of syllabi for most of the courses offered by the Computer and Information Science Department at Brooklyn College. (Professional Leadership: Committee Service) 2010
Member, Program Committee, Conference on Combinatorial Pattern Matching - CPM 2010. (Professional Leadership: Organizational Leadership Position) 2010
Member, review committee for Brooklyn College undergraduate research course CISC 5000. (Professional Leadership: Committee Service) 2010
Session chairwoman, CPM 2010 -- 21st Annual Symposium on Combinatorial Pattern Matching. (Professional Leadership: Organizational Leadership Position) 2010
Member, Program Committee for SPIRE'08, Symposium on String Processing and Information Retrieval. (Professional Leadership: Organizational Leadership Position) 2008