JSM 2005 Online Program

Abstract #302577

This is the preliminary program for the 2005 Joint Statistical Meetings in Minneapolis, Minnesota. Currently included in this program is the "technical" program, schedule of invited, topic contributed, regular contributed and poster sessions; Continuing Education courses (August 7-10, 2005); and Committee and Business Meetings. This on-line program will be updated frequently to reflect the most current revisions.

To View the Program:
You may choose to view all activities of the program or just parts of it at any one time. All activities are arranged by date and time.

The views expressed here are those of the individual authors
and not necessarily those of the ASA or its board, officers, or staff.

The Program has labeled the meeting rooms with "letters" preceding the name of the room, designating in which facility the room is located:

Minneapolis Convention Center = “MCC” Hilton Minneapolis Hotel = “H” Hyatt Regency Minneapolis = “HY”

Back to main JSM 2005 Program page

Legend:

= Applied Session,

= Theme Session,

= Presenter

Activity Number:	206
Type:	Invited
Date/Time:	Tuesday, August 9, 2005 : 8:30 AM to 10:20 AM
Sponsor:	SSC
Abstract - #302577
Title:	Distribution of the length of the longest common subsequence of two multi-state biological sequences
Author(s):	James C. Fu*+ and Wendy Lou
Companies:	University of Manitoba and University of Toronto
Address:	Department of Statistics, Winnipeg, MB, R3T 2N2, Canada
Keywords:	Runs and patterns ; Markov dependent trials ; Transition probability matrix ; Finite Markov chain imbedding
Abstract:	The length of the longest common subsequence (LCS) among two sequences has been used as a measure of similarity, and the application of this statistic is of importance in genomic studies. Even for the simple case of two sequences of equal length and composed of binary elements with equal probabilities, the exact distribution of the length of LCS remains an open question. This problem also is known as an NP-hard problem in computer science. Apart from combinatorial analysis, using the finite Markov chain imbedding technique, we derive the exact distribution for the length of LCS between two multistate sequences of different lengths. Numerical results are provided to illustrate the theoretical results.

The address information is for the authors that have a + after their name.
Authors who are presenting talks have a * after their name.

Back to the full JSM 2005 program