Walking tree heuristics for comparative genomic alignments.
Genomic sequence data is available for an ever-increasing number of organisms, but the full meaning of this data remains an enigma. String alignment is one approach for deciphering the information contained in genetic strings. Sequences which are conserved across species will help identify genes and other important structures. Similarity between species can be scored by measuring how well their sequences align. The walking tree method is an approximate string alignment method that can handle insertions, deletions, substitutions, translocations, and more than one level of inversion. We will describe this method and recent improvements which allow fast alignment of megabase strings. We will show examples in which the method located or discovered genes. We show how the method can be used to construct phylogenetic trees. We also show that the method can be used to identify essential regions for protein function.
Cavener
Jeffrey D
JD
Computer Science, Oregon State University, Corvallis, OR 97339, USA. wt@cavener.com
Cull
Paul
P
Holloway
James L
JL
Hsu
Tai-Ching
TC
D000818:Animals; D003196:Computer Graphics; D016678:Genome; D008957:Models, Genetic; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D013045:Species Specificity