CPM'96 Conference program announcement

Dan Hirschberg dan at verity.ICS.UCI.EDU
Fri Mar 15 02:04:14 EST 1996

            Laguna Beach, California
               June 10 - 12, 1996


Sunday June 9

7:00 p.m. - 9:30 p.m.  Reception and Registration

Monday June 10

8:00  Continental breakfast
8:30  Opening remarks

Session 1. Chair  Dan Hirschberg

8:45  Ricardo Baeza-Yates and Gonzalo Navarro.
      A faster algorithm for approximate string matching.

9:15  Nadia El-Mabrouk and Maxime Crochemore.
      Boyer-Moore strategy to efficient approximate string matching.

9:45  Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski,
      and Wojciech Rytter.
      Randomized efficient algorithms for compressed strings:
      The finger-print approach.

10:15 Erkki Sutinen and Jorma Tarhio.
      Filtration with q-Samples in approximate string matching.

10:45 Coffee Break

11:00 Invited Lecture: David Lipman (NCBI)
      Computing discoveries in molecular biology.

12:00 Lunch

Session 2. Chair  Rob Irving

1:30  Gerth Stolting Brodal and Leszek Gasieniec.
      Approximate Dictionary queries.

2:00  Robert Muth and Udi Manber.
      Approximate multiple strings search.

2:30  Chris Armen and Clifford Stein.
      A 2 2/3-approximation algorithm for the shortest
      superstring problem.

3:00  Snack Break

Session 3. Chair  Rao Kosaraju

3:30  Arne Andersson, N. Jesper Larsson, and Kurt Swanson.
      Suffix trees on words.

4:00  Dany Breslauer.
      The suffix tree of a tree and minimizing sequential transducers.

4:30  Martin Farach and S. Muthukrishnan.
      Perfect hashing for strings: Formalization and algorithms.

5:00  End of Session

8:00-9:00pm  Open Problems Session

Tuesday June 11

8:00  Continental breakfast

Session 4. Chair  Gad Landau

8:45  Mikhail S. Gelfand, Andrey A. Mironov, and Pavel A. Pevzner.
      Spliced alignment: A new approach to gene recognition.

9:15  Vincent Ferretti, Joseph H. Nadeau, and David Sankoff.
      Original synteny.

9:45  Piotr Berman and Sridhar Hannenhalli.
      Fast sorting by reversal.

10:15 Marie-France Sagot and Alain Viari.
      A double combinatorial approach to discovering patterns in
      biological sequences.

10:45 Coffee Break

11:00 Invited Lecture: Richard Arratia (USC)
      Poisson process approximation for repeats in one sequence and its
      application to sequencing by hybridization.

12:00 Lunch

Session 5. Chair  Sampath Kannan

1:30  Lusheng Wang and Dan Gusfield.
      Improved Approximation Algorithms for Tree Alignment.

2:00  Cynthia Phillips and Tandy J. Warnow.
      The asymmetric median tree - A new model for building consensus trees.

2:30  Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillip,
      and Gregory B. Sorkin.
      Constructing computer virus phylogenies.

3:00  Snack Break

Session 6. Chair  Pavel Pevzner

3:30  Bilha Sandak, Ruth Nussinov, and Haim J. Wolfson.
      Docking of conformationally flexible proteins.

4:00  William E. Hart and Sorin Istrail.
      Invariant patterns in crystal lattices:
      Implications for protein folding algorithms.

4:30  Dan Gusfield, Richard Karp, Lushen Wang, and Paul Stelling.
      Graph traversals, genes, and matroids:  An efficient case of
      the travelling salesman problem.

5:00  End of Session

6:00  Banquet

Wednesday June 12

8:00  Continental breakfast

Session 7. Chair  James Storer

8:45  Amihood Amir and Gruia Calinescu.
      Alphabet independent and dictionary scaled matching.

9:15  Kunsoo Park.
      Analysis of two-dimensional approximate pattern matching algorithms.

9:45  Srinivasa R. Arikati, Anders Dessmark, Andrzej Lingas,
      and Madhav Marathe.
      Approximation algorithms for maximum two-dimensional pattern matching.

10:15  Coffee Break

Session 8. Chair  Dennis Shasha

10:30  Kaizhong Zhang.
       Efficient parallel algorithms for tree editing problems.

11:00  James J. Fu.
       Approximate pattern matching in directed graphs.

11:30  Hans L. Bodlaender, Patricia A. Evans, and Michael R. Fellows.
       Finite-state computability of annotations of strings and trees.

12:00  Farewell

12:15  Lunch



All sessions of the symposium will be held at the Aliso Creek Inn in
Laguna Beach, California.  A block of rooms has been reserved at the
Aliso Creek Inn for participants.  Room reservations should be made
with the hotel using the Hotel Reservation Request Form.
The address of the hotel is

Aliso Creek Inn
31106 South Coast Highway
Laguna Beach, California 92677
Tel.: (714) 499-2271
Fax: (714) 499-4601


The closest major airport is John Wayne Airport (JWA) in Santa Ana,
about 16 miles (30 minutes) from the hotel.  A taxi ride costs about $30.
The largest nearby airport is Los Angeles International Airport (LAX),
about 40 miles (an hour) from the hotel.  A taxi ride costs about $85.

A cheaper alternative is to use the SuperShuttle van services available
at the airports [Orange County: (714)517-6600, Los Angeles: (213)775-6600].
Prices quoted in February were $25 from Orange County (one day advance
reservation required) and $50 from LAX (just show up) plus $9 per
additional passenger.

Some other shuttle services were surveyed in mid-1995.
Their rates are expressed as $X+Y,
indicating $X for the first person plus $Y for each additional person.
Most services require reservations a day or two in advance.
Advantage Airport Transportation Service (1-800-752-5211)
charges $35+0 from JWA and $65+0 from LAX for up to 5 people,
and does not require reservations for JWA since they are located there.
Southern California Coach (1-800-232-6224) charges $29+8 from JWA
and $48+8 from LAX.
AirTrans Express (1-800-870-7474) charges $28+7 from JWA and $43+7 from LAX.
ABC Shuttle (1-800-400-8060) charges $22+7 from JWA and $45+10 from LAX.


>From Los Angeles:  One hour south of L.A.
   Take the Santa Ana Freeway (I-5) or the San Diego Freeway (I-405)
   south to Laguna Freeway (#133).
   Travel south on #133 through Laguna Canyon, towards Laguna Beach.
   Turn south on Pacific Coast Highway (#1) 2 1/2 miles.
   Watch for overhead bridge after crossing Wesley Drive.
   Turn left at property sign immediately after passing under bridge.

>From San Diego:  One hour north of San Diego.
   Take the Santa Ana Freeway (I-5) north to the Beach Cities exit.
   Continue north on the Pacific Coast Highway (#1) 6 miles.
   Turn right at property sign, directly across from Aliso Beach and pier.

PROCEEDINGS: Springer-Verlag will publish the proceedings.  One copy is
included in the registration fee; additional copies may be purchased at
the symposium.

CLIMATE: The weather in Southern California is mildly warm in
June and is cool in the evenings.  Daytime temperatures in Laguna Beach
should be 75-80 F (24-27 C), with evenings about 60-65 F (15-18 C).

TOURISM: Combined with your trip to CPM'96 it is easy to spend a few
more days in California, for example, to visit Los Angeles or San Francisco.

Nearby attractions include
Aliso Creek State Beach: Located 365 yards from the resort.
Tide pools: Explore the fascinating marine tide pools located
     one-half mile north of Aliso Pier.
Dana Point Harbor: Visit the Marine Institute and historic
     tall ship, Pilgrim.  Whale watching and fishing charters available.
     Located 10 minutes south on Pacific Coast Highway.
San Juan Capistrano Mission: Experience California history in this
     beautiful mission, famous for Indian artifacts and the yearly return
     of the swallows.  Approximately 20 minutes east, Ortega exit off I-5.
Disneyland: The magical world of fantasy.  Located in Anaheim,
     approximately one hour north on Highway I-5.
Knotts Berry Farm: The Old West comes to life.
     Family entertainment, rides, restaurants, and shops.
     Located in Buena Park.  North on Highway I-5.
San Diego Wild Animal Park: See wild animals in their natural habitat.
     Located near Escondido.
San Diego Zoo: Internationally famous zoo featuring wide variety of
     exotic animals.  Approximately 1 1/4 hours south on I-5.
Sea World: Dolphins, whales, and other sea life provide outstanding
     shows daily.  Located in San Diego one hour south on I-5.
Laguna Beach: Charming small boutiques and art galleries.
     1 1/2 miles north on Pacific Coast Highway.
Fashion Island Mall: Fine outdoor shopping in Newport Beach.
     Approximately 20 minutes north on Pacific Coast Highway.
South Coast Plaza: One of the world's largest and highest volume shopping
     malls.  In Costa Mesa, approximately 40 minutes north, off I-405.

CPM INFORMATION: The first symposium on Combinatorial Pattern
Matching was held in Paris in 1990, followed by meetings in London,
Tucson, Padova, Pacific Grove, and Helsinki.  The seventh symposium
in Laguna Beach continues this tradition.


    D. Hirschberg (co-chair), R. Irving, S. Kannan,
    R. Kosaraju, G. Landau, A. Lesk, E. Myers (co-chair), P. Pevzner,
    D. Shasha, J. Storer, A. Yao, F. Yao.


A. Apostolico, M. Crochemore, Z. Galil, U. Manber.


D. Hirschberg.


CPM'96/ Dan Hirschberg
ICS Department
University of California at Irvine
Irvine, CA 92717-3425
Email:  cpm96 at ics.uci.edu
Tel.: (714) 824-6480
Fax:  (714) 824-4056


Registration fees may be paid by cash, check, or money order.  Checks
should be made payable to the Regents of the University of California.
If paying with a check drawn on a non-U.S. bank, add $30 to cover bank
processing charges.

The Conference Registration Form should be sent to the organizers as
soon as possible.  To avoid the late fee, the registration form must be
received by May 5 and the fees received by May 30.  The acceptance of
late registrations cannot be guaranteed because of space limitations.

The standard fee includes the Sunday night reception, Tuesday banquet,
lunches, coffee breaks, and one copy of the proceedings.  The student
fee includes all of the above except the banquet.  Students must present
a note from their department or supervisor verifying student status.

Accompanying persons are invited to the reception.  Additional tickets
for the conference banquet will be sold at the symposium.

The registration form is also available in our WWW server
( http://www.ics.uci.edu/~cpm96 ), where it can be filled interactively.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


               Before May 5    After May 5
Standard fee     ( ) $200       ( ) $250
Student fee      ( ) $ 80       ( ) $120






If requesting student registration, check here:_____ and
present a note from department or supervisor verifying student status.

Meal preference:   _____Standard   _____Vegetarian   _____Kosher

Mail to:

CPM'96 Registration
Department of Information and Computer Science
University of California at Irvine
Irvine, CA 92717-3425
Email: cpm96 at ics.uci.edu
Fax: (714) 824-4056

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

       Sunday, June 9th through Wednesday, June 12, 1996

                      ALISO CREEK INN
                  LAGUNA BEACH, CALIFORNIA

Your reservations must be received at the Hotel by April 9, 1996 or until
the room block has been filled.  Please check with reservations.
Hotel check-in, after 3:00pm.  Check out is at 12 Noon.
It may be necessary for people whose reservations arrive late
to stay at a nearby hotel.  If that should prove to be necessary, then
Aliso Creek will make every attempt to find suitable nearby accommodations
and will inform you.

Name:___________________________________________ # of guests:_____________


City:____________________________________ State:____________ Zip:_________

Home Phone:_________________________ Office Phone:________________________

Arrival Date:_______________________ Departure Date:______________________

Please check: ___Visa ___Master Card ___American Express ___Check enclosed

Account #:____________________________ *Deposit Amount $__________________

Expiration Date:_________________ Signature:______________________________

Room Rate:
           Single or Double Occupancy                    $97 + 10% tax
           $10 per additional person

*Deposit for your first night's lodging, of $106.70, must accompany your
reservation.  These deposits are refundable providing notice is received
by Aliso Creek Inn 48 hours prior to scheduled arrival date.

Account #5042

Mail to:
Aliso Creek Inn
31106 South Coast Highway
Laguna Beach, California 92677
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

More information about the Comp-bio mailing list