This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms in Bioinformatics, WABI 2007, held in Philadelphia, PA, USA in September 2007. The 38 revised full papers presented together with the abstract of a keynote talk were carefully reviewed and selected from 133 submissions. All current issues of algorithms in bioinformatics are addressed, ranging from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. Numerous biological problems are dealt with, including genetic mapping, sequence alignment and sequence analysis, phylogeny, comparative genomics, and protein structure. Furthermore the papers feature high-performance computing approaches to computationally hard learning and optimization problems in bioinformatics and cover methods, software and dataset repositories for development and testing of such algorithms and their underlying models. The refereed proceedings from the 7th International Workshop on Algorithms in Bioinformatics are provided in this volume. Papers address current issues in algorithms in bioinformatics, ranging from mathematical tools to experimental studies of approximation algorithms to significant computational analyses. Biological problems examined include genetic mapping, sequence alignment and analysis, phylogeny, comparative genomics, and protein structure. Shotgun Protein Sequencing (Keynote) 1(1) Pavel A. Pevzner Locality Kernels for Protein Classification 2(10) Evgeni Tsivtsivadze Jorma Boberg Tapio Salakoski When Less Is More: Improving Classification of Protein Families with a Minimal Set of Global Features 12(13) Roy Varshavsky Menachem Fromer Amit Man Michal Linial Fault Tolerance for Large Scale Protein 3D Reconstruction from Contact Maps 25(13) Marco Vassura Luciano Margara Pietro Di Lena Filippo Medri Piero Fariselli Rita Casadio Bringing Folding Pathways into Strand Pairing Prediction 38(11) Jieun K. Jeong Piotr Berman Teresa M. Przytycka A Fast and Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage 49(12) Loredana M. Genovese Filippo Geraci Marco Pellegrini Two Birds, One Stone: Selecting Functionally Informative Tag SNPs for Disease Association Studies 61(12) Phil Hyoun Lee Hagit Shatkay Genotype Error Detection Using Hidden Markov Models of Haplotype Diversity 73(12) Justin Kennedy Ion Mandoiu Bogdan Pasaniuc Haplotype Inference Via Hierarchical Genotype Parsing 85(13) Pasi Rastas Esko Ukkonen Seeded Tree Alignment and Planar Tanglegram Layout 98(13) Antoni Lozano Ron Y. Pinter Oleg Rokhlenko Gabriel Valiente Michal Ziv-Ukelson Inferring Models of Rearrangements, Recombinations, and Horizontal Transfers by the Minimum Evolution Criterion (Extended Abstract) 111(13) Hadas Birin Zohar Gal-Or Isaac Elias Tamir Tuller An ?(n2 / log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem 124(12) Mukul S. Bansal Oliver Eulenstein Incremental Discovery of Irredundant Motif Bases in Time O (|?|n2 log n) (Extended Abstract) 136(13) Alberto Apostolico Claudia Tagliacollo A Graph Clustering Approach to Weak Motif Recognition 149(12) Christina Boucher Daniel G. Brown Paul Church Informative Motifs in Protein Family Alignments 161(10) Hatice Gulcin Ozer William C. Ray Topology Independent Protein Structural Alignment 171(12) Joe Dundas T.A. Binkowski Bhaskar DasGupta Jie Liang Generalized Pattern Search and Mesh Adaptive Direct Search Algorithms for Protein Structure Prediction 183(11) Giuseppe Nicosia Giovanni Stracquadanio Alignment-Free Local Structural Search by Writhe Decomposition 194(2) Degui Zhi Maxim Shatsky Steven E. Brenner Defining and Computing Optimum RMSD for Gapped Multiple Structure Alignment 196(12) Xueyi Wang Jack Snoeyink Using Protein Domains to Improve the Accuracy of Ab Initio Gene Finding 208(8) Mihaela Pertea Steven L. Salzberg Genomic Signatures in De Bruijn Chains 216(12) Lenwood S. Heath Amrita Pati Fast Kernel Methods for SVM Sequence Classifiers 228(12) Pavel Kuksa Vladimir Pavlovic On-Line Viterbi Algorithm for Analysis of Long Biological Sequences 240(12) Rastislav Sramek Brona Brejova Tomas Vinar Predicting Protein Folding Kinetics Via Temporal Logic Model Checking (Extended Abstract) 252(13) Christopher James Langmead Sumit Kumar Jha Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops 265(12) Ankur Dhanik Peggy Yao Nathan Marz Ryan Propper Charles Kou Guanfeng Liu Henry van den Bedem Jean-Claude Latombe Algorithms for the Extraction of Synteny Blocks from Comparative Maps 277(12) Vicky Choi Chunfang Zheng Qian Zhu David Sankoff Computability of Models for Sequence Assembly 289(13) Paul Medvedev Konstantinos Georgiou Gene Myers Michael Brudno Fast Algorithms for Selecting Specific siRNA in Complete mRNA Data 302(8) Jaime Davila Sudha Balla Sanguthevar Rajasekaran RNA Folding Including Pseudoknots: A New Parameterized Algorithm and Improved Upper Bound 310(13) Chunmei Liu Yinglei Song Louis Shapiro HFold: RNA Pseudoknotted Secondary Structure Prediction Using Hierarchical Folding 323(12) Hosna Jabbari Anne Condon Ana Pop Cristina Pop Yinglei Zhao Homology Search with Fragmented Nucleic Acid Sequence Patterns 335(11) Axel Mosig Julian J.-L. Chen Peter F. Stadler Fast Computation of Good Multiple Spaced Seeds 346(13) Lucian Ilie Silvana Ilie Inverse Sequence Alignment from Partial Examples 359(12) Eagu Kim John Kececioglu Novel Approaches in Psychiatric Genomics (Keynote) 371(1) Maja Bucan The Point Placement Problem on a Line -- Improved Bounds for Pairwise Distance Queries 372(11) Francis Y.L. Chin Henry C.M. Leung W.K. Sung S.M. Yiu Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach 383(12) Alexander Schliep Roland Krause Efficient and Accurate Construction of Genetic Linkage Maps from Noisy and Missing Genotyping Data 395(12) Yonghui Wu Prasanna Bhat Timothy J. Close Stefano Lonardi A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence 407(13) Reka Albert Bhaskar DasGupta Riccardo Dondi Sema Kachalo Eduardo Sontag Alexander Zelikovsky Kelly Westbrooks Composing Globally Consistent Pathway Parameter Estimates Through Belief Propagation 420(11) Geoffrey Koh Lisa Tucker-Kellogg David Hsu P.S. Thiagarajan Author Index 431