Algorithmic Combinatorics on Words REU
June 6 - July 31, 2005 Schedule


Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8


All events are in room 335, Bryan Building, unless otherwise noted.



June 6 - June 12, 2005 (Week 1)


Monday, June 6

7:15 am arrive at Bryan Building room 335 to obtain parking permits (if applicable)
7:45 am arrive at Bryan Building room 335 (all)
8:30 am welcome breakfast
9:30 am orientation
1:00 pm tutorial on "Preliminaries on Partial Words" by Crystal Davis

Tuesday, June 7

8:45 am arrive at room 335 for identification cards
9:00 am discussion on the "Critical Factorization Theorem"
1:00 pm discussion on "Fine and Wilf's Periodicity Results and Consequences"

Wednesday, June 8

9:00 am discussion on "Unbordered Partial Words"
1:00 pm discussion on "Equations on Partial Words"
3:00 pm team creation

Thursday, June 9

9:30 am team meetings

Friday, June 10

9:30 am team meetings
3:00 pm tutorial on "Basic XHTML and CSS" by Margaret Moorefield
5:30 pm welcome dinner at Harper's Restaurant

Saturday, June 11

9:30 am team meetings

Return to Menu





June 13 - June 19, 2005 (Week 2)


Monday, June 13

9:30 am team meetings, individual LaTeX lessons

Tuesday, June 14

9:30 am team meetings, individual LaTeX lessons

Wednesday, June 15

9:30 am team meetings

Thursday, June 16

9:30 am team meetings

Friday, June 17

9:30 am team meetings

Saturday, June 18

9:30 am team meetings

Return to Menu





June 20 - June 26, 2005 (Week 3)


Monday, June 20

9:30 am team meetings

Tuesday, June 21

9:30 am team meetings
3:00 pm coffee
3:30 pm Guest speaker: Dr. Paul Duvall, UNCG and NSA

The Discrete Logarithm Problem

Abstract

The discrete logarithm problem is the basis for the security of a number of cryptographic systems, including the celebrated Diffee-Hellman protocol and the El Gamal system. In this talk, we will describe the problem and some applications, and discuss why it is believed to be difficult.

5:00 pm dinner at Liberty Oak Restaurant

Wednesday, June 22

9:30 am team meetings

Thursday, June 23

9:30 am team meetings

Friday, June 24

9:30 am team meetings
11:30 am lunch at Olive Garden Restaurant
1:00 pm Guest speaker: Ajay Chriscoe, IBM

Local periods and binary partial words: An algorithm

Abstract

The study of the combinatorial properties of strings of symbols from a finite alphabet (also referred to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics. Research in combinatorics on words goes back roughly a century. There is a renewed interest in combinatorics on words as a result of emerging new application areas such as molecular biology. Partial words were recently introduced in this context. The motivation behind the notion of a partial word is the comparison of genes (or proteins). Alignment of two genes (or two proteins) can be viewed as a construction of partial words that are said to be compatible.

While a word can be described by a total function, a partial word can be described by a partial function. More precisely, a partial word of length n over a finite alphabet A is a partial function from {1,...,n} into A. Elements of {1,...,n} without an image are called holes. A word is just a partial word without holes. The notion of a period of a word is central in combinatorics on words. In the case of partial words, there are two notions: one is that of period, the other is that of local period.

This paper extends to partial words with one hole the well known result of Guibas and Odlyzko which states that for every word u, there exists a word v of same length as u over the alphabet {0,1} such that the set of all periods of u coincides with the set of all periods of v. Our result states that for every partial word u with one hole, there exists a partial word v of same length as u with at most one hole over the alphabet {0,1} such that the set of all periods of u coincides with the set of all periods of v and the set of all local periods of u coincides with the set of all local periods of v.

To prove our result, we use the technique of Halava, Harju and Ilie, which they used to characterize constructively the set of periods of a given word. As a consequence of our constructive proof, we obtain a linear time algorithm which, given a partial word with one hole, computes a partial word with at most one hole over the alphabet {0,1} with the same length and the same sets of periods and local periods. A World Wide Web server interface at http://www.uncg.edu/mat/AlgBin/ has been established for automated use of the program.

2:30 pm break


Saturday, June 25

9:30 am team meetings

Return to Menu





June 27 - July 3, 2005 (Week 4)


Monday, June 27

9:30 am team meetings


Tuesday, June 28

9:30 am team meetings
3:00 pm coffee
3:30 pm Guest speaker: Dr. Nancy Green, UNCG (NSF CAREER Awardee)

Probabilistic Belief Networks for Modeling Genomic Health

Abstract

Project GenIE (http://www.uncg.edu/~nlgreen/GenIE-web-page.html) is using artificial intelligence knowledge representation and natural language generation techniques to create patient-tailored genomic health information. In this talk we describe our approach to modeling the patient's genomic health using probabilistic belief networks.


Wednesday, June 29

9:30 am team meetings

Thursday, June 30

9:30 am Presentation: "Critical Factorization Theorem" by Nathan Wetzler
10:30 am Presentation: "Critical Factorization Theorem" by Jeffery Zhang
1:00 pm Presentation: "Fine and Wilf's Periodicity Result on Partial Words and Consequences" by Kevin Corcoran and Jenell Nyberg

Friday, July 1

9:30 am Presentation: "Equations on Partial Words" by Dakota Blair and Rebeca Lewis
1:00 pm Presentation: "Unbordered Partial Words" by Jonathan Britton and Joel Dodge

Saturday, July 2

holiday

Return to Menu





July 4 - July 10, 2005 (Week 5)


Monday, July 4

holiday

Tuesday, July 5

9:30 am team meetings

Wednesday, July 6

9:30 am team meetings

Thursday, July 7

9:30 am team meetings

Friday, July 8

9:30 am team meetings

Saturday, July 9

9:30 am team meetings

Return to Menu





July 11 - July 17, 2005 (Week 6)


Monday, July 11

9:30 am team meetings
10:00 am Guest speaker: Stacy Duncan, Ph.D. Candidate, Iowa State University

Characterization of the finger loop domain of Ffh by random sequence libraries and sequence analysis

Abstract

Although the role of the function of the signal recognition particle (SRP) from Escherichia coli in targeting of proteins to the cytoplasmic membrane is known, details of many of its structural features require further study. The finger loop region of the Ffh protein is essential for SRP function and likely forms part of the binding site for hydrophobic membrane targeting sequences. To investigate the sequence and structural features of this domain important for its function, we have developed a genetic system to screen a random aptamer library for sequences that restored function to a finger loop deletion mutant. About 1% of random sequences can replace the wild type finger loop. Analysis of the random sequences, as well as targeted mutagenesis, shows the importance of hydrophobicity in finger loop function. All functional sequences also lack extensive secondary structural consistent with the role of the finger loop in binding a variety of ligands. Continued isolation and analysis of random sequences should provide new insights into how the finger loop functions in membrane protein targeting.

11:30 am lunch at Lucky 32 restaurant
1:00 pm team meetings

Tuesday, July 12

9:30 am team meetings

Wednesday, July 13

9:30 am team meetings

Thursday, July 14

9:30 am team meetings

Friday, July 15

9:30 am team meetings

Saturday, July 16

9:30 am team meetings

Return to Menu





July 18 - July 24 2005 (Week 7)


Monday, July 18

9:30 am team meetings

Tuesday, July 19

9:30 am team meetings

Wednesday, July 20

9:30 am team meetings

Thursday, July 21

9:30 am team meetings

Friday, July 22

9:30 am team meetings

Saturday, July 23

9:30 am team meetings

Return to Menu





July 25 - July 31, 2005 (Week 8)


Monday, July 25

9:30 am team meetings

Tuesday, July 26

9:30 am team meetings

Wednesday, July 27

9:30 am team meetings

Thursday, June 28

9:30 am team meetings

Friday, July 29

10:00 am Presentation: "Unbordered Partial Words" by Jonathan Britton and Joel Dodge
11:00 am Presentation: "Equations on Partial Words" by Dakota Blair and Rebeca Lewis
1:00 pm Presentation: "Fine and Wilf's Periodicity Result on Partial Words and Consequences" by Kevin Corcoran and Jenell Nyberg
2:00 pm Presentation: "Critical Factorization Theorem" by Jeffery Zhang
3:00 pm Presentation: "Critical Factorization Theorem" by Nathan Wetzler

Saturday, July 30

10:00 am farewell picnic at Hanging Rock State Park

Return to Menu