Combinatorics Of Genome Rearrangements Guillaume Fertin

Combinatorics Of Genome Rearrangements Guillaume
Fertin download
https://ebookbell.com/product/combinatorics-of-genome-
rearrangements-guillaume-fertin-56635880
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Combinatorics Of Genome Rearrangements 1st Edition Guillaume Fertin
https://ebookbell.com/product/combinatorics-of-genome-
rearrangements-1st-edition-guillaume-fertin-5674744
Combinatorics Of Coxeter Groups Anders Bjrner Francesco Brenti
https://ebookbell.com/product/combinatorics-of-coxeter-groups-anders-
bjrner-francesco-brenti-49161284
Combinatorics Of Train Tracks Am125 Volume 125 R C Penner John L Harer
https://ebookbell.com/product/combinatorics-of-train-tracks-
am125-volume-125-r-c-penner-john-l-harer-51950442
Combinatorics Of Compositions And Words 1st Edition Silvia Heubach
https://ebookbell.com/product/combinatorics-of-compositions-and-
words-1st-edition-silvia-heubach-2012990

Combinatorics Of Symmetric Designs Ionin Yj Shrikhande Ms
https://ebookbell.com/product/combinatorics-of-symmetric-designs-
ionin-yj-shrikhande-ms-2044432
Combinatorics Of Spreads And Parallelisms Johnson N
https://ebookbell.com/product/combinatorics-of-spreads-and-
parallelisms-johnson-n-2044640
Combinatorics Of Permutations 2nd Edition 2nd Edition Mikls Bna
https://ebookbell.com/product/combinatorics-of-permutations-2nd-
edition-2nd-edition-mikls-bna-21963828
Combinatorics Of Set Partitions Mansour Toufik
https://ebookbell.com/product/combinatorics-of-set-partitions-mansour-
toufik-22057116
Combinatorics Of Permutations Miklos Bona Bona Miklos
https://ebookbell.com/product/combinatorics-of-permutations-miklos-
bona-bona-miklos-22380802

Combinatorics of
Genome Rearrangements
Guillaume Fertin, Anthony Labarre, Irena Rusu, Éric T annier, and Stéphane Vialette
computational biol ogy
Combinatorics of Genome Rearrangements
Guillaume Fertin, Anthony Labarre, Irena Rusu, Éric T annier, and Stéphane Vialette
From one cell to another, from one individual to another, and from one species to another, the content of DNA molecules is often
similar. The organization of these molecules, however, differs dramatically, and the mutations that affect this organization are
known as genome rearrangements. Combinatorial methods are used to reconstruct putative rearrangement scenarios in order
to explain the evolutionary history of a set of species, often formalizing the evolutionary events that can explain the multiple
combinations of observed genomes as combinatorial optimization problems. This book offers the first comprehensive survey of
this rapidly expanding application of combinatorial optimization. It can be used as a reference for experienced researchers or as
an introductory text.
Genome rearrangement problems have proved so interesting from a combinatorial point of view that the field now belongs as
much to mathematics as to biology. This book takes a mathematically oriented approach, but provides biological background
when necessary. It presents a series of models, beginning with the simplest (which is progressively extended by dropping
restrictions), each constructing a genome rearrangement problem. The book also discusses an important generalization of
the basic problem known as the median problem, surveys attempts to reconstruct the relationships between genomes and
phylogenetic trees, and offers a collection of summaries and appendixes with useful additional information.
Guillaume Fertin is Professor of Computer Science at the University of Nantes. Anthony Labarre received a PhD in Mathematics
and Computer Science from the Université Libre de Bruxelles. Irena Rusu is Professor of Computer Science at the University of
Nantes. Éric Tannier is a Researcher in the Laboratory of Biometrics and Evolutionary Biology of the University of Lyon. Stéphane
Vialette is a Researcher in the Gaspard-Monge Institute of Electronics and Computer Science at the University of Paris-Est
Marne-la-Vallée.
Computational Molecular Biology series
“Combinatorics of Genome Rearrangements is the first computer science monograph on this rapidly expanding field. The authors
have managed the seemingly impossible feat of combining scope and coherence; they have pulled together all the disparate
research lines and integrated them through a common treatment and notation. This volume is simultaneously an accessible
computational biology textbook for computer science and bioinformatics students, an easy and thorough entry to the field
for professionals attracted by the novelty and diversity of the problems in the field, and an up-to-date reference book for
specialists.”
David Sankoff, Department of Mathematics and Statistics, University of Ottawa
“This book will be a defining book for the field of genome rearrangement and is destined to become a classic as soon as it
hits the bookshelves. The authors have done an excellent job in presenting one of the most technically challenging areas of
computational biology in an easily understood manner. Dobzhansky and Sturtevant would not be disappointed.”
Pavel Pevzner, Ronald R. Taylor Chair of Computer Science, Director, Interdisciplinary Bioinformatics Program, University of
California, San Diego
The MIT Press
Massachusetts Institute of T echnology
Cambridge, Massachusetts 02142
http://mitpress.mit.edu
Fertin, Labarre, Rusu, T annier, and Vialette
Combinatorics of Genome Rearrangements
978-0-262-06282-4

Combinatorics of Genome Rearrangements

Sorin Istrail, Pavel Pevzner, and Michael Waterman, editors
Computational molecular biology is a new discipline, bringing together computa-
tional, statistical, experimental, and technological methods, which is energizing and
dramatically accelerating the discovery of new technologies and tools for molecular
biology. The MIT Press series on Computational Molecular Biology is intended to
provide a unique and e¤ective venue for the rapid publication of monographs, text-
books, edited collections, reference works, and lecture notes of the highest quality.
Computational Molecular Biology: An Algorithmic Approach
Pavel A. Pevzner, 2000
Computational Methods for Modeling Biochemical Networks
James M. Bower and Hamid Bolouri, editors, 2001
Current Topics in Computational Molecular Biology
Tao Jiang, Ying Xu, and Michael Q. Zhang, editors, 2002
Gene Regulation and Metabolism: Postgenomic Computation Approaches
Julio Collado-Vides, editor, 2002
Microarrays for an Integrative Genomics
Isaac S. Kohane, Alvin Kho, and Atul J. Butte, 2002
Kernel Methods in Computational Biology
Bernhard Scho¨lkopf, Koji Tsuda, and Jean-Philippe Vert, editors, 2004
An Introduction to Bioinformatics Algorithms
Neil C. Jones and Pavel A. Pevzner, 2004
Immunological Bioinformatics
Ole Lund, Morten Nielsen, Claus Lundegaard, Can Kes¸mir, and Søren Brunak,
2005
Ontologies for Bioinformatics
Kenneth Baclawski and Tianhua Niu, 2005
Biological Modeling and Simulation: A Survey of Practical Models, Algorithms, and
Numerical Methods
Russell Schwartz, 2008
Combinatorics of Genome Rearrangements
Guillaume Fertin, Anthony Labarre, Irena Rusu, E´ric Tannier, and Ste´phane
Vialette, 2009

Combinatorics of Genome Rearrangements
Guillaume Fertin, Anthony Labarre, Irena Rusu, E´ric Tannier and Ste´phane Vialette
The MIT Press
Cambridge, Massachusetts
London, England

62009 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical
means (including photocopying, recording, or information storage and retrieval) without permission in
writing from the publisher.
For information about special quantity discounts, please email [email protected]
This book was set in Times New Roman and Syntax on 3B2 by Asco Typesetters, Hong Kong.
Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Combinatorics of genome rearrangements / Guillaume Fertin . . . [et al.].
p. cm. — (Computational molecular biology)
Includes bibliographical references and index.
ISBN 978-0-262-06282-4 (hardcover : alk. paper) 1. Translocation (Genetics)—Mathematical models.
2. Translocation (Genetics)—Data processing. 3. Combinatorial analysis. 4. Genomics—Mathematics.
I. Fertin, Guillaume, 1972– II. Series.
[DNLM: 1. Gene Rearrangement. 2. Genome. 3. Models, Genetic. QU 470 C731 2009]
QH462.T7C66 2009
572.8
0
77—dc22 2008042152
10987654321

Contents
Preface xiii
Acknowledgments xv
1 Introduction 1
1.1 A Minimalist Introduction to Molecular Evolution 1
1.2 Birth of the Combinatorics of Genome Rearrangements 4
1.3 Statement of the Problem 6
1.4 Scope of This Survey 7
1.5 Overview of the Models 7
1.6 Organization of the Book 8
I DUPLICATION-FREE MODELS: PERMUTATIONS 11
2 Genomes as Permutations 13
2.1 The Symmetric Group 13
2.2 The Cycles of a Permutation 14
2.3 Signed Permutations 15
2.4 Distances on Permutation Groups 15
2.4.1 Rearrangements as Generators 16
2.4.2 Invariant Distances 17
2.5 Circular Permutations 18
2.5.1 Classical Circular Permutations 19
2.5.2 Genomic Circular Permutations 19
2.6 First Measures of Similarity between Permutations 20
2.6.1 Breakpoints 20
2.6.2 Common Intervals and Semipartitive Families 21
3 Distances between Unsigned Permutations 25
3.1 Transposition Distance 25
3.1.1 Lower Bounds on the Transposition Distance 26
3.1.2 Upper Bounds 29
3.1.3 Improving Bounds Using Toric Permutations 32

3.1.4 Easy Cases 33
3.1.5 Approximation Algorithms 34
3.1.6 Conjectures and Open Problems 35
3.2 Preﬁx Transposition Distance 36
3.2.1 Lower Bounds 37
3.2.2 Upper Bounds 38
3.2.3 Diameter 38
3.2.4 Easy Cases 39
3.2.5 Approximation Algorithms 39
3.2.6 Variant: Insertion of the Leading Element 40
3.3 Reversal Distance 40
3.3.1 Lower Bounds 40
3.3.2 Upper Bounds 43
3.3.3 Easy Cases 43
3.3.4 Computational Complexity 44
3.3.5 Approximation Algorithms 45
3.3.6 Exact Algorithms 46
3.4 Preﬁx Reversal Distance (Pancake-Flipping) 47
3.4.1 Lower Bounds 47
3.4.2 History 48
3.4.3 Variants 48
3.5 Variants 49
3.5.1 Block Interchange Distance 49
3.5.2 Element Interchange Distances 50
3.5.3 Weighted Reversals 52
3.5.4 Fixed-Length Reversals 54
3.5.5 Bounded Variants 54
3.5.6 Cut-and-Paste 55
3.5.7 Strip Moves 55
3.5.8 Stack-Sorting 56
3.5.9 Tandem Duplications and Random Losses 58
3.5.10 Combined Operations: Reversals and Transpositions 59
3.6 Relations between Distances on Unsigned Permutations 61
4 Distances between Signed Permutations 63
4.1 Conserved Interval Distance 63
4.2 Signed Reversal Distance 64
4.2.1 Reversals 64
4.2.2 The Distance Formula 65
4.2.3 The Scenario of Reversals 67
4.2.4 The Space of All Optimal Solutions 68
4.2.5 Experimental Results 69
4.3 Variants of Sorting by Reversals 69
4.3.1 Perfect Signed Reversal Distance 69
4.3.2 Preﬁx Reversals (Burned Pancakes) 70
4.3.3 Reversals That Are Symmetric around a Point 70
vi Contents

4.3.4 Weighted Reversals 71
4.3.5 Fixed-Length Reversals 71
4.4 Combined Operations 72
4.4.1 Reversals and Transpositions 72
4.4.2 Reversals, Transpositions, Transreversals, Revrevs 72
4.5 Double Cut-and-Joins 73
5 Rearrangements of Partial Orders 75
5.1 Genomes as Partially Ordered Sets 75
5.2 Partially Ordered Sets 75
5.2.1 Basic Deﬁnitions 75
5.2.2 Representing Posets 77
5.2.3 Topological Sorting 77
5.3 Constructing a Poset 78
5.4 Reversal Distance 79
5.5 Breakpoint Distance 80
5.5.1 Exact Algorithms 80
5.5.2 Heuristics for Computing the Breakpoint Distance 81
6 Graph-Theoretic and Linear Algebra Formulations 83
6.1 Simple Permutations and the Interleaving Graph 83
6.2 The Overlap Graph 84
6.3 The Local Complementation of a Graph 85
6.4 The Matrix Tightness Problem 85
6.5 Extension to Sorting by Transpositions 86
6.6 The Intermediate Case of Directed Local Complementation 87
II MODELS HANDLING DUPLICATIONS: STRINGS 89
7 Generalities 91
7.1 Biological Motivations 91
7.2 Strings and Rearrangements on Strings 92
7.3 Balanced Strings 94
7.4 How to Deal with Multiple Copies? 95
8 Distances between Arbitrary Strings 97
8.1 The Match-and-Prune Model 98
8.1.1 Breakpoint Distance 100
8.1.2 Signed Reversal Distance 106
8.1.3 Adjacency Similarity 108
8.1.4 Common Intervals Similarity 111
8.1.5 Conserved Intervals Similarity 113
8.1.6 Conserved Intervals Distance 114
8.1.7 MAD and SAD Numbers 118
8.1.8 Heuristics 119
Contents vii

8.2 The Block Edit Model 123
8.2.1 Block Covering Distance 123
8.2.2 Symmetric Block Edit Distance 126
8.2.3 Large Block Edit Distance 129
8.2.4 String Edit Distance with Transpositions 130
8.2.5 Signed Strings 131
9 Distances between Balanced Strings 133
9.1 Minimum Common String Partition Problems 133
9.1.1 Unsigned MCSP 134
9.1.2 Signed MCSP 135
9.1.3 Reversed MCSP 137
9.1.4 Full Breakpoint Distance 138
9.2 Reversal Distance 138
9.2.1 Unsigned Reversals 138
9.2.2 Signed Reversals 141
9.2.3 Sorting by Reversals with Length-Weighted Costs 142
9.2.4 Preﬁx Reversals on Unsigned Strings (Pancake-Flipping) 144
9.2.5 Reversals of Length at Most 2 147
9.3 Unsigned Transpositions 147
9.3.1 Unit Cost Transpositions 147
9.3.2 Length-Weighted Transpositions 150
9.3.3 Restricted Length-Weighted Transpositions 150
9.3.4 Preﬁx Transpositions 152
9.3.5 Adjacent Swaps 153
9.4 Unsigned Block Interchanges 153
9.4.1 Unit-Cost Block Interchanges 153
9.4.2 Character Swaps 155
9.5 Relations between Distances 157
III MULTICHROMOSOMAL MODELS 159
10 Paths and Cycles 161
10.1 Genomes 161
10.2 Breakpoints 162
10.3 Intervals 163
10.4 Translocation Distance 164
10.4.1 Feasibility 166
10.4.2 Unsigned Genomes 166
10.4.3 Signed Genomes 167
10.4.4 Translocations Preserving Centromeres 168
10.4.5 Variants and Special Cases 169
10.5 Double Cut-and-Joins (2-Break Rearrangement) 170
10.6k-Break Rearrangement 171
10.7 Fusions, Fissions, Translocations, and Reversals 172
10.8 Rearrangements with Partially Ordered Chromosomes 174
viii Contents

11 Cycles of a Permutation 175
11.1 A Model for Multichromosomal Circular Genomes 175
11.2 A Generalization to Signed Genomes 178
11.2.1 A Different Kind of Signed Permutation 178
11.2.2 The Operations 179
11.2.3 Some Results 179
12 Set Systems and the Syntenic Distance 181
12.1 Introduction 181
12.2 Structural Properties 182
12.2.1 Compact Representation 182
12.3 Lower Bounds 184
12.4 Diameter 185
12.5 Algorithmic Results 185
12.5.1 Syntenic Distance 185
12.5.2 Easy Cases 186
12.6 Conjectures and Open Problems 189
IV MULTIGENOMIC MODELS 191
13 Median and Halving Problems 193
13.1 Breakpoint Median 194
13.1.1 Complexity 194
13.1.2 Algorithms 195
13.2 Reversal and DCJ Median 197
13.2.1 Complexity 197
13.2.2 Algorithms 197
13.2.3 Variants 198
13.3 Duplicated Genomes 199
13.3.1 The Double Distance 199
13.3.2 Genome Halving 201
13.3.3 Solving Tetraploidy 202
13.3.4 Guided Halving 202
13.3.5 Genome Halving with Unordered Chromosomes 203
13.4 Other Variants, Generalizations, and Discussion 205
13.4.1 Other Operations 205
13.4.2 More Permutations in the Input 205
13.4.3 Medians and Centers 205
13.4.4 Discussion 206
14 Rearrangement Phylogenies 207
14.1 The Large Parsimony Problem 207
14.2 The Large Parsimony Problem with Gene Orders 209
14.2.1 Breakpoint and Reversal Phylogenies on Permutations 209
14.2.2 Variants 211
Contents ix

14.3 Heuristics for the Breakpoint/Reversal Phylogeny Problem 211
14.3.1 Tree Steinerization 212
14.3.2 Sequential Addition 216
14.3.3 Character Encodings 217
14.4 Variants 220
V MISCELLANEOUS 221
15 Software 223
15.1 Pairwise Rearrangements 223
15.1.1 Unichromosomal Models 223
15.1.2 Multichromosomal Models 225
15.2 Phylogeny Reconstruction and Medians 226
15.2.1 BPAnalysis 226
15.2.2 MGR 226
15.2.3 GRIL 226
15.2.4 GRAPPA 227
15.2.5 MedRbyLS 227
15.2.6 rEvoluzer and amGRP 227
15.2.7 GENESIS 228
16 Open Problems 229
16.1 Complexity Issues 229
16.1.1 Hardness 229
16.1.2 Approximability 230
16.1.3 Polynomial Complexity 231
16.2 Diameter 231
16.3 Tightness of Bounds 232
APPENDICES 233
A Graph Theory 235
A.1 Undirected Graphs 235
A.1.1 Basic Deﬁnitions 235
A.1.2 Paths and Cycles 236
A.1.3 Connectivity 237
A.1.4 Bipartite Graphs 238
A.1.5 Trees and Forests 238
A.1.6 Matching 238
A.1.7 Adjacency Matrix 239
A.2 Directed Graphs 240
A.2.1 Basic Deﬁnitions 240
A.2.2 Paths and Cycles 241
A.2.3 Connectivity 241
A.2.4 Directed Acyclic Graphs 241
x Contents

B Complexity Theory 243
B.1 The ClassNP243
B.1.1NP-Optimization Problems: FromPTAStoAPX246
B.1.2NP-Optimization Problems: BeyondAPX250
B.1.3 Parameterized Complexity 250
B.2 SomeNP-Complete Problems 252
Glossary 257
Bibliography 263
Index 283
Contents xi

Preface
In 1984, at a congress in Paris, Franc¸ois Jacob, one of the most famous evolutionary
scientists, stated that ‘‘La mole´cule de l’he´re´dite´est raboute´e, modiﬁe´e, coupe´e, ral-
longe´e, raccourcie, retourne´e’’ (the molecule of heredity is sewed together, modiﬁed,
cut, lengthened, shortened, reversed) during evolution. From one cell to another, one
individual to another, one species to another, the content of the DNA molecules is
often similar, but their organization often di¤ers dramatically. The mutations that
a¤ect this organization are calledgenome rearrangements, and the structural di¤er-
ences between molecules in two genomes motivate the study of their combinatorics.
Indeed, the inference of the evolutionary events that can explain the multiple combi-
nations of observed genomes can often be formalized as combinatorial optimization
problems.
The variety of problems that have been raised in this domain is so interesting from
a combinatorial point of view that this ﬁeld has grown and become partly indepen-
dent of the application, so that it now belongs as much to mathematics as to biology.
The mathematics and algorithmics related to genome rearrangements have witnessed
a huge expansion over these last years, and this dynamics seems to be continuing at
the present time. Due to this success, the ﬁeld has swallowed other studies that were
developed earlier and without biological motivations. For example, many problems
about sorting permutations with constraints are now presented as rearrangement
problems, without considering the biological relevance of the constraint.
Although molecular biology gave birth to it, combinatorics of genome rearrange-
ments is now a mathematical and algorithmic ﬁeld that has found its own coherence.
It has its own important results, many peripheral developments, and its famous open
problems. A great interest of this domain is the simplicity of the formulation of the
problems, compared to the sometimes great complexity or even nonexistence of so-
lutions. Moreover, the fact that the subject has now been studied for nearly two de-
cades and has been discussed only in specialized research literature motivates both a
thorough survey of the topic and an introduction to a broader audience. This book
intends to fulﬁll both goals.

Acknowledgments
Se`verine Be´rard, Gae¨lle Giberti, and Julien Moncel participated in the birth of the
project that led to the present book. The decision to undertake this work was made
during a meeting in Lyon funded by the ACI ‘‘Nouvelles Interfaces des Mathe´ma-
tiques,’’p-vert, led by Marie-France Sagot.
Anthony Labarre was funded by the Fonds pour la Formation a`la Recherche
dans l’Industrie et dans l’Agriculture (FRIA), by a grant from the Fonds National
de la Recherche Scientiﬁque (FNRS), and by Communaute´Franc¸aise de Belgique—
Actions de Recherche Concerte´es. He wishes to thank his family and friends, as well
as his adviser Jean-Paul Doignon. Eric Tannier was funded by the French National
Research Institute for Computer Science (INRIA) and by the Agence Nationale de
la Recherche (ANR), projects JC05_49162 (GENOMICRO) and NT05-3_45205
(REGLIS).

1
Introduction
Although this book is combinatorially inclined and does not devote much discussion
to the biological issues, we will start with a short introduction to molecular evolu-
tion, for conceptual and historical purposes; indeed, this is where the combinatorial
study of genome rearrangements originates, and the invention of most variants of
genome rearrangement problems are still driven by biological constraints. This intro-
duction is not necessary to understand the combinatorial problems and their solu-
tions, but it allows us to place them in their context and explain why they are
important, independently of their mathematical value.
1.1 A Minimalist Introduction to Molecular Evolution
The ‘‘molecules of heredity,’’ the support of genetic information, are present in every
cell of all living organisms (bacteria, plants, animals, etc.). Each molecule is called a
chromosome, and the set of all chromosomes is what we will call thegenome. Chro-
mosomes are made ofDNA(deoxyribonucleicacid), a double-stranded molecule in
which eachstrandis a long succession ofnucleotides(asequence). Nucleotides can
be of four types—A,C,G, andT—and the two DNA strands are coupled in such a
way that anAon one strand is always coupled with aTon the other strand, and aC
on one strand is always coupled with aGon the other strand. Those strands are said
to becomplementary: the sequence on one strand determines the sequence on the
other one. Figure 1.1 shows a representation of the above concepts.
Because of complementarity, a DNA molecule is usually represented as a single
sequence (one arbitrary strand), but the organization in two strands will often be cru-
cial for our purpose. Chromosomes can be either circular (the sequence forms a circle
and has no ends), which is often the case in bacteria, or linear (the sequence has two
ends, calledtelomeres), which is often the case in animals and plants. Asegmentof
DNA is a part of this molecule made of consecutive nucleotides. Ageneis a segment
of DNA that contains the information needed to construct the other molecules in the
cell.

What accounts for the diversity of living organisms is the possibility for DNA to
replicateitself with some inaccuracy: one genome is used to produce another, almost
identical genome. This inaccuracy is the principle of molecularevolution.
A DNA molecule may evolve bypoint mutations(i.e., mutations at the level of
nucleotides). There are three di¤erent kinds of point mutations: substitutions (one
nucleotide is replaced with another), insertions (a nucleotide is added to the se-
quence), and deletions (a nucleotide is removed from the sequence). Detecting these
events is the goal ofsequence alignment(for a presentation of this topic, see, for ex-
ample, Setubal and Meidanis [333] or Jones and Pevzner [224]).
Figure 1.1
A chromosome and a fragment of a DNA molecule
Source: National Institutes of Health, National Human Genome Research Institute, Division of Intra-
mural Research
2 1 Introduction

However, a sequence may also evolve by modifying its organization at a larger
scale. These large-scale mutations are calledrearrangements,orstructural variations,
and detecting them is the goal ofgenome rearrangementproblems. The main rear-
rangements include the following:
Deletions. A segment of the genome is lost (see ﬁgure 1.2).
Transpositions. A segment of the genome moves to another location (see ﬁgure 1.3).
Transpositions are sometimes referred to as translocations or insertions, but transpo-
sition is well adopted in the ﬁeld of combinatorics of genome rearrangements.
Inversionsorreversals. A segment of the genome is reversed and the strands are
exchanged (see ﬁgure 1.4).
Duplications. A segment of DNA is copied and inserted in the genome. There are
three main standard types of duplications:tandem duplications, illustrated by ﬁgure
1.5, which insert the copy next to the original;retrotranspositions, which insert a
copy of a gene at an arbitrary location in the genome; andwhole genome duplica-
tions, which copy either the whole genome or some of its chromosomes.
Figure 1.2
Deletion of the dotted region in a chromosome
Figure 1.3
Transposition of the dotted region in a chromosome
Figure 1.4
Reversal of the underlined segment, resulting in the boxed segment
Figure 1.5
Tandem duplication of the dotted region in a chromosome
1.1 A Minimalist Introduction to Molecular Evolution 3

Reciprocal translocation. A segment of a chromosome that contains a telomere is
exchanged with a segment of another chromosome that also contains a telomere
(see ﬁgure 1.6).
Fusion. Two chromosomes are joined into one (see ﬁgure 1.7).
Fission. One chromosome splits into two (this is the inverse of a fusion).
Horizontal,orlateral,transfer. A segment of the genome is copied from one
genome to another. This is common mainly in unicellular organisms.
All these operations act on a genome at the level of DNA segments rather than on
nucleotides. This is why a genome is often represented by a sequence of segments in
that setting: they are the segments that are found in an almost identical state in sev-
eral species, not cut by rearrangements. Two segments are said to behomologousif
they derive from a common ancestor and are distinguished by a replication event
(they end up in two di¤erent genomes) or by a duplication event (they both belong
to the same genome).
Genes are often taken as those homologous segments because, due to their func-
tional utility, they are less subject to small mutations and are rarely cut by rearrange-
ments, which is not the case for other parts of the genome.
1.2 Birth of the Combinatorics of Genome Rearrangements
In 1936 two renowned biologists, Dobzhansky (the inventor of the synthetic theory
of evolution) and Sturtevant (the discoverer of rearrangement processes in genomes
at the beginning of the twentieth century) proposed for the ﬁrst time to use the degree
Figure 1.6
Reciprocal translocation of the dotted regions in two chromosomes
Figure 1.7 Fusion of two chromosomes
4 1 Introduction

of disorder between the organization of genes in two di¤erent genomes as an indica-
tor of an evolutionary distance between organisms (see Dobzhansky and Sturtevant
[145, 146]). They proposed a scenario of inversions to explain chromosomal di¤er-
ences between 17 groups of ﬂies, as well as a reconstruction of putative ancestral gene
arrangements and species histories from the observation of the gene order along the
chromosomes.
Since rearrangements are relatively rare events, scenarios minimizing their number
are more likely to be close to reality. In 1941 Sturtevant and Novitski [343] formu-
lated the problem of minimizing the number of inversions that may explain the dif-
ferences in arrangements between two species: ‘‘. . . for each such sequence there was
determined the minimum number of successive inversions required to reduce it to the
ordinal sequence chosen as ‘standard.’ For numbers of loci above nine the determi-
nation of this minimum number proved too laborious, and too uncertain, to be car-
ried out. . . .’’
The reconstruction of genome rearrangements from the examination of chromo-
somes, using techniques such as ‘‘chromosome banding’’ or ‘‘in-situ hybridisation’’
[301] were numerous, all focusing on relatively close species, so that the number of
rearrangements was small. All these studies were based on the parsimony criterion,
which makes molecular biologists often prefer explanations of di¤erences between
genomes that involve as few mutations as possible. This principle makes the connec-
tion with combinatorial optimization possible, because the optimization principle
meets the parsimony criterion.
As we entered the genome sequencing era, the importance of rearrangements in
evolution or illnesses was pointed out by several biologists, such as Palmer and Her-
bon [289], who examined the di¤erences in the gene order of the mitochondrial
genomes of cabbage and turnip, which are very similar in sequence but dramatically
di¤erent in structure. It was not until 1982 that some researchers working in combi-
natorial optimization started to formalize and become involved in this problem, in
order to overcome the limit of nine genes stated by Sturtevant and Novitski [343].
Watterson et al. [369] proposed to represent the relative positions of genes in di¤erent
genomes aspermutations. In order to propose an evolutionary scenario between two
species, one had to solve the problem of transforming one circular permutation into
another with a minimum number of inversions. The problem was far from being
solved after this ﬁrst article, but it was well stated.
Transforming one permutation into another by means of a minimum number of
allowed operations is often equivalent tosortinga permutation by means of the
same operations (see page 17). Though it took a decisive start in a biological context,
the problem of sorting permutations with constraints was not new: a few mathemati-
cians and computer scientists had already tackled that kind of problem in the past.
Those problems were not, however, motivated by biology: constraints were related
1.2 Birth of the Combinatorics of Genome Rearrangements 5

to data structures as stacks, or were simply introduced as games that later turned out
to be particular cases of genome rearrangement problems, or found uses in other
ﬁelds.
New models were later proposed to handle more operations, duplicated segments,
and several chromosomes. Shortly after Watterson et al. [369], the ﬁeld started its
dramatic expansion.
1.3 Statement of the Problem
Thegenome rearrangement problemis formulated in its most general form as follows:
given a set of genomes and a set of possible evolutionary events, ﬁnd a shortest set of
events transforming those genomes into one another.
What ‘‘genome’’ means here, and what events are, makes the diversity of the prob-
lem. Miscellaneous models have been proposed, depending on various parameters,
and we brieﬂy review them in section 1.5. ‘‘Shortest’’ usually refers to the number of
events, but it may also mean ‘‘of least weight’’ if events are weighted (e.g., according
to their probability of occurrence).
The length (or weight) of an optimal sequence of events transforming one genome
into another is called thedistancebetween the two genomes. We will often require
that this distance be a metric on the set of genomes, in the mathematical sense, and
we recall its deﬁnition here.
Definition 1.1Ametricdon a setSis an application
d:SS!R:ðs;tÞ7 !r
satisfying the following three axioms:
1. For alls;tAS,dðs;tÞb0 anddðs;tÞ¼0 if and only ifs¼t(positivity).
2. For alls;tAS,dðs;tÞ¼dðt;sÞ(symmetry).
3. For alls;t;uAS,dðs;uÞadðs;tÞþdðt;uÞ(triangular inequality).
A setSequipped with a metricd
is called ametric spaceand is denotedðS;dÞ.
Finding an optimal sequence of events between two genomes of course yields the dis-
tance between the two genomes, but the converse is not always true. Therefore, most
of the time we will examine both aspects of the problem. A related problem we will
be interested in is that of determining thediameterof a metric space.
Definition 1.2Thediameterof a metric spaceðS;dÞis the maximal value the dis-
tance can reach, that is,
max
s;tAS
dðs;tÞ:
6 1 Introduction

1.4 Scope of This Survey
This survey is restricted to the algorithmic and combinatorial aspects of genome rear-
rangements, but it also encompasses a few problems that are similar in spirit, even if
they were not motivated by biology in the ﬁrst place. The motivation for this is two-
fold: ﬁrst, those problems deserve at least to be mentioned here, since they are closely
related to genome rearrangement problems; and second, the study of related prob-
lems or variants of our problems may provide insight on the original problems we
are interested in.
There has been a lot of work on probabilistic models and statistical studies of
genome rearrangement problems, which we will not consider in this work. We refer
the reader to the surveys of Eriksson [165] and Durrett [150]. As the reader may have
guessed by reading section 1.1, we also will not delve much into the biological
aspects, and will focus on the mathematical aspects of genome rearrangements,
though we will mention applications and biological contexts where appropriate.
Some partial surveys have been published in earlier articles or book chapters. In
1995, Hannenhalli and Pevzner [197] wrote the ﬁrst survey on the combinatorics of
genome rearrangements, mainly based on their success at sorting signed permuta-
tions by reversals (see sections 3.3 and 4.2). The chapters by Pevzner [296] and Setu-
bal and Meidanis [333] dedicated to genome rearrangements mainly focus on sorting
permutations by reversals. The books edited by Gascuel [182], Sanko¤ and Nadeau
[322], Bo¨ckenhauer and Bongartz [74], Jiang et al. [222], and Tseng and Zelkowitz
[360] contain chapters that survey part of the ﬁeld or try to give a quick overview of
it. A survey article by Li et al. [247] reveals the importance and popularity of the
ﬁeld, and this book intends to be a more developed version of it.
1.5 Overview of the Models
Depending on the assumptions that are made on the data, or the events we want to
study, di¤erent models can be used. The basic objects will behomologous markers
(i.e., segments of genomes that can be found in several species, leading to the belief
that they belonged to the common ancestor of these species). Genes are a good exam-
ple of such markers, though they are not the only ones; but since genes were histori-
cally ﬁrst used as markers for genome rearrangement studies, we often say ‘‘genes’’
for ‘‘homologous markers,’’ as a simpliﬁcation.
We will start with the simplest possible model, and progressively extend it by drop-
ping restrictions. In the case where
1. the order of genes in each genome is known,
2. all genomes share the same set of genes,
1.5 Overview of the Models 7

3. all genomes contain a single copy of each gene, and
4. all genomes consist of a single chromosome,
genomes are modeled bypermutations(see page 13): each gene can be assigned a
unique number and is found exactly once in each genome.
As explained in section 1.1, a DNA molecule has two strands, and some rear-
rangements may change the strand that a segment belongs to. Therefore, each seg-
ment may be assigned aþor asign (þis omitted most of the time) to indicate
the strand it resides on, leading to the model ofsigned permutations(see page 15).
We have also seen in section 1.1 that chromosomes can be linear or circular, and the
latter case can be modeled using circular permutations rather than linear (classical)
ones.
In spite of all the technical progress that has been made over the last decades and
the large number of genomes that have been completely sequenced, many genomes
have been only partially sequenced, which means that we cannot model them using
permutations because genes are not totally ordered. In that case, genomes can never-
theless be modeled bypartially ordered sets, and some studies can still be conducted
using that model, as we will see in chapter 5.
In general, however, genes do not appear exactly once in each genome: due to
duplications and deletions, there can be several copies of a gene in a given genome,
or no copy at all. In that case, genomes are modeled bystrings(on the alphabet of
genes, see page 91) rather than permutations. Of course, it is possible to sign the ele-
ments of the string or to deal with circular strings.
A great part of living organisms have a genome that consists of several chromo-
somes (in a variable number, which can lie between 1 and 100), as is the case for all
animals, and permutations as we have presented them are no longer a realistic model
in that case. One can use thedisjoint cycle decompositionof permutations (see page
14) to represent each chromosome using a cycle, in the case where chromosomes are
circular, but this concept does not extend to linear chromosomes or strings since it
cannot model duplicated genes. We may therefore want to extend our model to dis-
joint sets of paths and cycles (page 159), where each path or cycle models a chromo-
some.
Finally, one may not care about or simply not know the order of genes in each
chromosome, and care only about whether two genes are insynteny(i.e., whether
they belong to the same chromosome). In that case, genomes are modeled bycollec-
tionsofsetsof genes (see chapter 12).
1.6 Organization of the Book
The ﬁrst three parts of this book are organized according to the models presented in
the previous section, each part being devoted to a mathematical object that has been
8 1 Introduction

used to construct genome rearrangement problems. Part IV is devoted to an impor-
tant generalization of the basic genome rearrangement problem, known as theme-
dian problem, which aims at considering more than two genomes at the same time
and inferring their common ancestors. It surveys the attempts to reconstruct the kin
relationships between genomes by drawingphylogenetic treesin which nodes are an-
cestral conﬁgurations and branches (edges) account for evolutionary events.
Part V is a collection of summaries that provide useful additional information on
the ﬁeld, such as a list of available software based on the algorithms that we describe
in the book and a list of open problems. This book also includes two appendices:
appendix A is devoted to basic concepts of graph theory, and appendix B recalls
the basics of the algorithmic theory of complexity, as well as a fewNP-complete
problems.
1.6 Organization of the Book 9

I
DUPLICATION-FREE MODELS: PERMUTATIONS

2
Genomes as Permutations
Permutations were the ﬁrst mathematical objects to serve as formal models for study-
ing arrangements of DNA fragments among several species. Studies that use permu-
tations in this context make use of a common knowledge (either classical or invented
ad hoc) that is worth discussing here before stating our ﬁrst genome rearrangement
problems. More information about permutation group theory can be found in the
books by Bo´na [76] and Wielandt [370].
2.1 The Symmetric Group
Permutations are functions, which we will also view as orderings of a given ﬁnite set.
Definition 2.1Apermutationpis a bijection over the setf1;2;...;ng. The image of
iAf1;2;...;ngbypis denoted byp
i. The elementsp iof the permutation are called
genes.
A permutation induces a total orderonf1;2;...;ng: we writep
i0pjifi<j.
A classical notation used in combinatorics to denote a permutationpis thetwo-row
notation
12 n
p
1p2p n

;
we will adopt the traditional notation used in the genome rearrangement literature
by keeping only the second row, that is,
p¼ðp
1p2p nÞ:
We refer to permutations as deﬁned in deﬁnition 2.1 aslinear permutations,as
opposed to other kinds of permutations that will be introduced later.
The classicalmultiplicationorcompositionof permutations is applied, as the com-
position of functions, from right to left: when writingps, we ﬁrst applys,thenp,

which results in the permutationðp s1
ps2
p sn
Þ. For example, ifp¼ð3142Þand
s¼ð4132Þ, thenps¼ð2341Þ. This operation induces a group structure on the
set of all permutations. Indeed, composition is associative; theidentity permutation
i¼ð12nÞis the corresponding neutral element; and theinverse permutationofp
is the permutationp
1
obtained by exchanging positions and elements inp, that is,
p
1
p
i
¼ifor 1aian.
Definition 2.2Thesymmetric group, denoted byS n, is the set of all permutations of
f1;2;...;ngwith the operation.
2.2 The Cycles of a Permutation
Orderings are by no means the only possible representation of permutations: another
representation is the well-knowndisjoint cycle decomposition.
Definition 2.3Acycleof a permutationp, denoted byC¼ði 1;i2;i3;...;i k1;ikÞis a
set of elements such that for 1ajak1,p
ij
¼ijþ1andp ik
¼i1.
Every permutation decomposes into the product of disjoint cycles, and this decom-
position is unique (up to ordering of the cycles and of the elements within each cycle).
For example, the permutation (4 8 9 7 6 5 1 3 2 10) decomposes into the cycles (1, 4,
7), (2, 8, 3, 9), (5, 6), and (10). Note the distinction between the two notations: for
instance,ð12nÞis the identity permutation, whereasð1;2;...;nÞis the permuta-
tionð234n1n1Þ. A natural graphical representation of permutations follows
from this decomposition.
Definition 2.4Thegraph of a permutationpinS nis the directed graph with vertex
setf1;2;...;ngand with edge setfði;p
iÞj1aiang.
The cycles of this graph are the cycles of the permutationp. Figure 2.1 shows a
representation of the graph of (489765132 10).
Definition 2.5All permutations that have the same disjoint cycle decomposition
form aconjugacy class.
Figure 2.1
Graph of the permutation (4 8 9 76513210)
14 2 Genomes as Permutations

For example,p¼ð1;2;3Þð4;5;6Þands¼ð1;3;5Þð2;4;6Þbelong to the same con-
jugacy class. This is the particular case for the symmetric group of the general notion
of a conjugacy class in any group.
Definition 2.6A permutation isevenif the number of even cycles in its disjoint cycle
decomposition is even or, equivalently, if it can be expressed as a product of an even
number of 2-cycles. Otherwise, it isodd.
Definition 2.7Thealternating group Anis the subgroup ofS nformed by all even per-
mutations.
2.3 Signed Permutations
Signed permutations model the organization of genomes better than unsigned per-
mutations, because they take into account the double helix structure of DNA. In-
deed, given one arbitrary starting point for a chromosome, each DNA strand has
an orientation, and by complementarity, the orientation of one strand is the reverse
of the orientation of the other. This orientation corresponds to the direction in which
genes are transcribed on a given strand.
Definition 2.8Asigned permutationonf1;2;...;ngis a permutation of the set
fn;...;2;1;1;2;...;ngthat satisﬁesp
i?p i.
The one-row notation that was mentioned in section 2.1 in the context of unsigned
permutations is also used for signed permutations. For example, the permutation
43211 234
314 2 2413

is simply denoted by
ð2413Þ;
in which we drop the mapping of the negative elements since keeping it would be re-
dundant, according to deﬁnition 2.8. Composition and inversion of signed permuta-
tions are well deﬁned. The neutral element for the operationremains the identity
permutationi¼ð12nÞ.
Definition 2.9Thehyperoctahedral group, denoted byS
G
n
, is the set of all signed per-
mutations offn;...;2;1;1;2;...;ngwith the operation.
2.4 Distances on Permutation Groups
In this section, we useGto denote a permutation group, either signed or unsigned.
2.4 Distances on Permutation Groups 15

2.4.1 Rearrangements as Generators
Permutations may represent not only genomes, but also mutations (rearrangements),
in such a way that a mutationrwill transform a genomepinto the genomepr.
For example, for a permutationp, the reversal of the segmentp
i;...;p jði<jÞin
the permutationpis modeled by the permutation
r¼ð1i1jj1iþ1ijþ1nÞ
or, in the signed case,
r¼ð1i1j?j1Þ ðiþ1?ijþ1nÞ;
and
pr¼ðp
1p i1pjpj1p iþ1pipjþ1p nÞ
or, in the signed case,
pr¼ðp
1p i1pjpj1 p iþ1pipjþ1p nÞ:
Therefore, computing a sequence of rearrangements that transforms a permutation
pinto a permutationscomes down to ﬁnding a sequencer
1;...;r
ksuch that
pr
1r
k¼sor, equivalently,s
1
p¼r
1
k
r
1
1
.
If the set of allowed rearrangements is such that it is always possible to obtain any
permutation inGby composing those rearrangements, they are said to begenerators
ofG. In this case, rearrangement problems on permutations can be formulated as
follows:
Given any two permutationspandsinGand a setSof generators ofG, ﬁnd a
minimum length factorization ofs
1
pthat consists only of elements ofS.
Problems related to the factorization of permutations had been studied long before
mathematicians became interested in genome rearrangement problems. There are
some general complexity results that prevent us from hoping for a general solution
to the problem: Even and Goldreich [168] have shown that ﬁnding such a factoriza-
tion isNP-hard, and Jerrum [221] has shown that the problem isPSPACE-complete,
even ifjSj¼2. Some of these problems are easy to solve, however, if the set of gen-
erators is ﬁxed, and not part of the instance: well-known examples include the case
whereSis the set of all exchanges of elements, whether they are adjacent (in which
case an optimal sorting algorithm is the well-known ‘‘bubble sort’’; see Knuth [237])
or not (in which case it corresponds to factorization of permutations into 2-cycles, a
problem ﬁrst solved by Cayley [100]). Jerrum [221] gives a few other examples of
such tractable problems.
Generators of a permutation group yield the following natural graphical represen-
tation, which is fundamental in group theory.
16 2 Genomes as Permutations

Definition 2.10Given a setSof generators of a permutation groupG, theCayley
graphassociated withðS;GÞis the graph whose vertices are the elements ofGand
whose edges connect two vertices such that the corresponding elements can be trans-
formed into one another using an element ofS.
Figure 2.2 shows the Cayley graph associated withðS;S
4Þ, whereSis the set of all
exchanges of adjacent elements, andS
4is the group of all linear unsigned permuta-
tions of 4 elements. The notion of diameter introduced in deﬁnition 1.2 has a natural
interpretation in that setting: it is the length of the ‘‘longest shortest path’’ between
any two vertices of the Cayley graph corresponding to the given group and set of
generators.
2.4.2 Invariant Distances
Given a set of generators of a permutation group, a distance between two permuta-
tionspandscan be deﬁned as the minimum number of generatorsr
1;...;r
ksuch
thatpr
1r
k¼s. This is indeed a distance, according to deﬁnition 1.1. The
distances we consider satisfy an additional property that allows us to reduce genome
rearrangement problems to a simpler canonical problem.
Figure 2.2
The Cayley graph associated withðS;S
4Þ, whereSis the set of all exchanges of adjacent elements, also
known as thepermutohedronof order 4
Based on a picture by David Eppstein
2.4 Distances on Permutation Groups 17

Definition 2.11A distancedonGisleft-invariantif for allp,s,tinG, we have
dðp;sÞ¼dðtp;tsÞ:
Left-invariance can be intuitively explained as follows. Given two genomes that
can be represented as permutations of the same set of genes, the number of opera-
tions that will be required to transform one genome into the other does not depend
on how genes are numbered: one can arbitrarily assign a unique number to each gene
and ‘‘rename’’ the genes in the other genome accordingly, without modifying the cor-
responding distance between the two genomes. Left-invariance is an important un-
derlying concept in genome rearrangements because it is the reason why many
problems considered in that ﬁeld reduce to a sorting problem: indeed, computing
the distance of interest between any two permutationspandsis by left-invariance
equivalent to computing the distance between permutationss
1
pandi, and we
can therefore restrict our attention to computing the distance between a permutation
and the identity. An immediate corollary of this property is that for all those dis-
tances and any permutationpinG, we havedðp;iÞ¼dðp
1
;iÞ. Since most of the
time we will be considering the distance of a permutation from the identity, we will
abbreviatedðp;iÞintodðpÞ.
Definition 2.12Given a permutationp, a sequence ofkrearrangementsr
1;...;r
kis
called asorting sequenceforpifpr
1r
k¼i.
As the reader might wonder, there is also a concept known asright-invariance, but
most distances used in genome rearrangements do not satisfy this property. We note,
however, that right-invariant distances between permutations have applications in
statistics (see Diaconis [135]) and in the theory of adaptive sorting algorithms (see
Estivill-Castro and Wood [166]).
2.5 Circular Permutations
Circular permutations model circular chromosomes. They are especially relevant be-
cause most unichromosomal genomes actually consist of a circular chromosome
(bacteria are a notable example). They also model the evolution of mitochondrial
and chloroplastic genomes, which are small, independent circular chromosomes
found in the cells of all animals and plants, as well as the ‘‘nuclear genome,’’ which
most often contains several linear chromosomes.
We deﬁne two kinds of circular permutations: the ‘‘classical’’ ones, found in the
mathematical literature, and the ‘‘genomic’’ circular permutations with equivalence
classes that are a bit broader than in the classical case: permutations are supposed
to model chromosomes, and since linear chromosomes have no prescribed starting
point, circular chromosomes have no preferred reading direction (clockwise or coun-
18 2 Genomes as Permutations

terclockwise). Usually this information is not taken into account in studies of linear
chromosomes as permutations. This can be justiﬁed by the study of chromosome seg-
ments. But it cannot be justiﬁed for circular permutations, for which it is necessary to
take into account the fact that they may be read in both directions.
2.5.1 Classical Circular Permutations
Let ﬁrst1

be the equivalence relation between signed or unsigned linear permuta-
tions deﬁned as follows: we writep1

sif there exists an integerksuch that for alli
inf1;2;...;ng,p
i¼s
ðiþkmodnÞþ1 . In other words,pandsare equivalent ifpcan be
obtained by rotating the elements ofs(or conversely). An equivalence class under
this relation is called a (signed or unsigned)circular permutation, and may be denoted
using any of its elements.
In order to avoid confusion between linear and circular permutations, we use the
notation½p
1p2p nto denote circular permutations; therefore, we have
½p
1p2p n?f?p 1p2p nÞ;ðp2p3p np1Þ;...;ðp np1p n1Þg:
We will also use the

symbol to explicitly denote circular permutations without
expanding their content. For instance,pis a linear permutation, whereasp

is a cir-
cular one. Ifp¼ðp
1p nÞis a linear (signed or unsigned) permutation, we refer to
the circular permutationp
e
¼½p1p nnþ1as its correspondingcircular exten-
sion. Any linear permutation in the equivalence class of a circular permutationp

is
called alinearizationofp

.
2.5.2 Genomic Circular Permutations
The following deﬁnition corresponds to how circular permutations are often
described in combinatorics of genome rearrangement literature (see, e.g., Meidanis
et al. [265], Solomon et al. [342]). Let1

be the relation between signed or unsigned
linear permutations deﬁned as follows: we writep1

sif
either there exists an integerksuch that for alliinf1;2;...;ng,p i¼s
ðiþkmodnÞþ1
orðp 1;...;p nÞ¼ðs n;...;s 1Þifpandsare unsigned, andðp 1;...;p nÞ¼
ðs
n;...;s 1Þifpandsare signed.
In other words,pandsare in relation ifpcan be obtained by rotating the elements
ofsor by reversing the whole set of elements, ﬂipping the signs for signed permuta-
tions. The transitive closure of1

is an equivalence relation, and an equivalence
class under this equivalence relation is called a (signed or unsigned)genomic circular
permutation, and may be denoted using any of its elements.
For each problem involving circular permutations, we will mention whether it is
solved for classical or genomic circular permutations. Note that given one genomic
2.5 Circular Permutations 19

signed circular permutation such that one linearizationpcontains only elements with
aþsign, the subclass containing all permutations in which all elements have aþsign
corresponds to the classical unsigned circular permutation ofp. This observation will
lower the number of di¤erent variants to consider.
2.6 First Measures of Similarity between Permutations
Some measures of similarity and dissimilarity between permutations (they are nu-
merous in the literature; see, for example, the survey by Estivill-Castro and Wood
[166]) are used in computational biology, even if they do not explicitly correspond
to rearrangement events. They are nevertheless useful, and we present here two
examples based on concepts that will be used by other distances we will introduce
later.
2.6.1 Breakpoints
Introduced by Sanko¤ and Blanchette [317].
Complexity: polynomial. Computing the distance and diameter is a trivial problem,
contained in the deﬁnition.
One of the ﬁrst intuitions inspired by the parsimony criterion is that if a group of
genes appears consecutively in several species, then they must have been present in
the same order in the ancestral species, and were not separated during evolution.
This translates mathematically into the notions of adjacencies and breakpoints,
which, despite their simplicity, deserve a clariﬁcation because their deﬁnition in the
literature varies according to the models and operations under consideration (see
also a discussion on multichromosomal genomes in section 10.2).
Definition 2.13Thelinear extensionof a (signed or unsigned) permutationpof
f1;2;...;ngis the permutation off0;1;...;nþ1gdeﬁned byp
l
¼ð0p 1p nnþ1Þ.
For the linear extension of signed permutations, it is a convention that 0 has a pos-
itive sign.
Definition 2.14Letp
l
be the linear extension of a (signed or unsigned) permutation
ponf1;2;...;ng.Apointofpis an ordered pairðp
l
i
;p
l
iþ1
Þfor 0aian. Moreover:
Ifp
l
iþ1
¼p
l
i
þ1, it is called anadjacency;
Ifp
l
iþ1
¼p
l
i
1, it is called areverse adjacency;
If it is not an adjacency, it is called abreakpoint;
If it is neither an adjacency nor a reverse adjacency, it is called astrong breakpoint.
20 2 Genomes as Permutations

For a circular permutationp

, itscanonical linearizationis the linearization ofp

placing the last elementnat the last position. Note that a genomic unsigned permu-
tation has two canonical linearizations, and a classical signed permutation may have
none. In this case, deﬁne the canonical linearization as the one of the corresponding
genomic permutation. We say that the points, adjacencies, reverse adjacencies, and
breakpoints are the points, adjacencies, reverse adjacencies, and breakpoints of the
linear permutationðp
1p2pn1Þ, wherepis a canonical linearization. Note that in
genomic unsigned permutations, adjacencies correspond to reverse adjacencies, and
breakpoints to strong breakpoints.
We illustrate those concepts by the following example: points are indicated by
s
in the permutation (0
4
8
9
7
6
5
1
3
2
10). Of all those points, (8, 9) is an
adjacency; (7, 6), (6, 5), and (3, 2) are reverse adjacencies; and all other points are
breakpoints.
The number of points and breakpoints of a permutationp(be it signed or
unsigned, linear or circular) are denoted bypðpÞandbpðpÞ, respectively. Moreover,
we use the notationsbðpÞfor the number of strong breakpoints. Note that ifp

is a
circular permutation off1;2;...;ng, thenpðp

Þ¼n, and ifpis a linear permutation
off1;2;...;ng, thenpðpÞ¼nþ1.
Breakpoints yield a ﬁrst simple example of an evolutionary distance between
genomes: thebreakpoint distancebetween two permutationspandsis deﬁned as
bpðp;sÞ¼bpðs
1
pÞ. This distance is trivial to compute, and some authors have
argued that it is not less realistic than others (see, e.g., Sanko¤ and Blanchette
[317]). It corresponds to the number of adjacencies in one permutation that are not
adjacencies in the other. It is extended to circular permutations by applying the same
formula, removing elementnfrom the linearization wherenis the last element.
2.6.2 Common Intervals and Semipartitive Families
Common intervals are an extension of adjacencies that model the fact that groups of
genes stay together in a genome, but not necessarily in the same order or with the
same direction.
Definition 2.15Aninterval(orsegment) of a permutationpis a setfjp aj;jpaþ1j;...;
jp
b1j;jpbjg, with 1aaaban.
The elementsp
aandp bare theextremitiesof the interval.
Definition 2.16A setIis said to be acommon intervalof permutationspandsif it is
an interval of bothpands.
In the particular case wheres¼i, an intervalI¼fjp
aj;...;jp bjgofpis a common
interval (common topandi) if, givenm¼min
iA½a;bjpijandM¼max
iA½a;bjpij,I
2.6 First Measures of Similarity Between Permutations 21

contains all integers in the range½m;M, which is equivalent to requiring that
Mm¼ba.
As an example, let us consider the permutation (8 9 7 6 5 3 1 4 2 10); its nontrivial
(i.e., we do not list singletons nor the whole permutation) common intervals with re-
spect toiare indicated as line segments below.
89765314210
Computing the set of common intervals of two permutations is both easy and very
interesting, because it raises a modular structure of di¤erences between permutations
that can be useful in many rearrangements studies. (For a method of construction,
see, for example, Bui et al. [91]).
Definition 2.17Two common intervals of permutationspandsare said tooverlapif
they intersect and neither of them is contained in the other. A common interval is
calledstrongif it does not overlap any other common interval.
Definition 2.18Thestrong interval treeof permutationspandsis the graph whose
vertex set is the set of strong intervals ofpands, and which contains an edge be-
tween two strong intervalsI
1andI 2ifI1HI2and there is no other strong interval
I
3such thatI 1HI3JI2. This graph is a tree rooted at the intervalf1;2;...;ng,so
that each node has one parent and possibly several children, ordered according to
their position in both permutations.
Lemma 2.1(See, for example, Bui et al. [91].) LetIbe a strong interval of two per-
mutationspands. One of the following is true:
Figure 2.3
Example of a PQ-tree of common intervals for the permutation (8 97653142 10). Linear nodes are
drawn as rectangles, and prime nodes are represented as ellipses
22 2 Genomes as Permutations

No union of children ofIin the tree of strong intervals is a common interval ofp
ands; in this caseIis calledprime.
All the subsets that are the union of consecutive children are common intervals ofp
ands; in that caseIis calledlinear.
Definition 2.19The strong interval tree is called aPQ-tree, and the prime nodes are
identiﬁed asP-nodes; linear nodes are identiﬁed asQ-nodes.
All these notions are immediately useful for common intervals of permutations,
since the family of common intervals of two permutations is weakly partitive and
linear. Figure 2.3 shows an example of a PQ-tree of a family of common intervals.
Bergeron et al. [49] use the structure of common intervals to infer a metric between
permutations, whereas Bernt et al. [65] use the structure of common intervals to give
a hint on the type of rearrangements that have occurred for speciﬁed instances.
2.6 First Measures of Similarity Between Permutations 23

3
Distances between Unsigned Permutations
Unsigned permutations were the ﬁrst combinatorial model of genomes for the study
of rearrangements (see Watterson et al. [369]), and are still used when the orientation
of the markers is not known, as is the case, for example, when the data come fromin
situ hybridization(see Wienberg [371]). All permutations in this chapter are unsigned,
unless explicitly stated otherwise.
3.1 Transposition Distance
We begin our survey of permutation-related genome rearrangement problems with
the operation oftransposition(the term ‘‘transposition’’ comes from biology and
refers totransposons, which are sequences of DNA that can be displaced in a
genome. They therefore have nothing to do withalgebraic transpositionsto which
mathematicians are used). Transpositions consist in displacing an interval of the per-
mutation or, equivalently, in exchanging two contiguous intervals of the permuta-
tion. However simple the problem of sorting by transpositions might seem, a lot of
questions remain open, the most notable being the complexity of the sorting problem
and computing the associated distance, as well as the diameter of the symmetric
group under this operation.
Introduced by Bafna and Pevzner [30].
Complexity: unknown.
Best approximation ratio:
11
8
by Elias and Hartman [160].
Diameter: unknown. Lies between
nþ1
2

(see Bafna and Pevzner [30]) and
2n
3
(see
Eriksson et al. [164]).
Definition 3.1For any permutationpinS n, thetranspositiontði;j;kÞwith
1ai<j<kanþ1 applied topexchanges the intervals determined respectively
byiandj1 and byjandk1, transformingpintoptði;j;kÞ. Therefore,
tði;j;kÞis the following permutation:

1i1iiþ1j2j1jjþ1k1kn
1i1jjþ1k1iiþ1j2j1kn
!
:
Thetransposition distanceof a permutationpwill be denoted bytdðpÞ. Table 3.1
shows the distribution of the transposition distance for 1ana10.
For a (classical) circular permutationp

, the action of a transposition can be mod-
eled on the intervals of any of its linearizations. The problem of sorting a circular
permutation by transpositions is equivalent to the problem of sorting linear permuta-
tions by transpositions, as proved, for example, by Hartman [201]. Indeed, it is easy
to see that any transposition on an arbitrary linearization has the same result as an-
other transposition on a canonical linearization. No study of the transposition dis-
tance of genomic circular permutations has been reported.
3.1.1 Lower Bounds on the Transposition Distance
3.1.1.1 Lower Bounds Based on Breakpoints
It can easily be seen that one transposi-
tion can decrease the number of breakpoints by at most three, as illustrated by the
following example:
ð51
324Þ!ð51234Þ:
This yields a ﬁrst lower bound on the transposition distance.
Theorem 3.1[30] For allpinS n, we havetdðpÞb
bpðpÞ
3
.
Breakpoints can be categorized into two di¤erent classes, which are well known in
the literature of sorting procedures: breakpoints such thatp
iþ1>piare called
Table 3.1
The number of permutationspinS
nwithtdðpÞ¼k
n
k 01 2 3 4 5 6 7
110000000
211000000
314100000
4 1 10 12 1 0 0 0 0
5 1 20 68 31 0 0 0 0
6 1 35 259 380 45 0 0 0
7 1 56 770 2,700 1,513 0 0 0
8 1 84 1,932 13,467 22,000 2,836 0 0
9 1 120 4,284 52,512 191,636 114,327 0 0
10 1 165 8,646 170,907 1,183,457 2,010,571 255,053 0
26 3 Distances between Unsigned Permutations

ascents, and breakpoints such thatp iþ1<piare calleddescents. We usedesðpÞto de-
note the number of descents in a permutationp.
It can be easily checked that whereas the number of breakpoints may decrease by
three through the application of a transposition, the number of descents can decrease
only by two (see our above example in the case of breakpoints). Sinceihas no de-
scent, we immediately have a lower bound of
desðpÞ
2
. However, it should be noted
that, contrary to the number of breakpoints and to the transposition distance, the
number of descents in a permutation may di¤er from the number of descents in its
inverse. This yields a second lower bound, mentioned by Eriksson et al. [164].
Theorem 3.2[164] For allpinS n,
tdðpÞbmax
desðpÞ
2
;
desðp
1
Þ
2

:
An observation related to breakpoints allows us to restrict our study of sorting by
transpositions to a particular class of permutations characterized by the following
idea: since the identity permutation is the only permutation with no breakpoint, a
ﬁrst intuitive sorting strategy would be to preserve adjacencies and ‘‘repair’’ break-
points. A lemma by Christie [115] conﬁrms that the intuition of preserving adjacen-
cies always leads to an optimal solution.
Lemma 3.1[115] For a permutationp, there exists an optimal sorting sequence of
transpositions that never breaks the adjacencies ofp.
Every permutationpcan be uniquely transformed into a permutation with no
adjacency without a¤ecting its distance, by partitioningpinto strips.
Definition 3.2Astripis a maximal interval ofpcontaining no breakpoint.
Thereduced permutationcorresponding topis obtained by discarding the leftmost
(resp. rightmost) strip if it begins with 1 (resp. if it ends withn), then keeping the
minimal element of each strip inp, and ﬁnally renumbering the remaining ele-
ments appropriately. For example, the reduced permutation corresponding to
(
45631782), in which strips are underlined, is (4 3 1 5 2), through replacing
strips 4 5 6 and 7 8. Lemma 3.1 implies that the transposition distance of the reduced
permutation is the same as the transposition distance ofp, and we can therefore re-
strict our attention to sorting reduced permutations.
3.1.1.2 Lower Bounds Based on the Cycle GraphThe cycle graph of a permutation,
introduced by Bafna and Pevzner [30], is one of the many variants of a perva-
sive structure that has proved most useful in obtaining theoretical results on genome
3.1 Transposition Distance 27

rearrangement problems. Indeed, most important results in the ﬁeld (e.g., bounds,
approximation algorithms, or formulas for computing rearrangement distances)
make an extensive use of parameters based on the cycle graph or on a close structure.
Definition 3.3Thecycle graphof a permutationpoff1;2;...;ngis the directed
graphGðpÞwith vertex setf0;1;...;n;nþ1gand whose arcs consist in
black(orreality) arcsðp
l
i
;p
l
ði1Þ
Þfor 1aianþ1,
gray(ordesire) arcsði;ðiþ1ÞÞfor 0aian,
wherep
l
is the linear extension ofp(see deﬁnition 2.13).
Reality arcs represent what we have (the permutationp), whereas desire arcs indi-
cate what we want to obtain (the permutationi). Each vertex of the cycle graph has
one incoming arc of each color and one outgoing arc of each color. As a straight-
forward consequence, the cycle graph decomposes in a single way intoalternating
cycles(i.e., cycles that alternate black and gray arcs). The number of alternating
cycles inGðpÞis denoted bycðGðpÞÞ.
Figure 3.1 shows the cycle graph of a linear permutation. It is straightforward to
deﬁne the cycle graph using the circular extension instead of the linear extension:
identify 0 andnþ1 in deﬁnition 3.3. This gives the circular layout of the cycle graph
used in ﬁgure 3.2, which is frequently encountered in the literature. Since sorting a
permutation, its linear extension or its circular extension is equivalent, any model
can be preferred for devising bounds or algorithms.
Since the identity permutationiis the only permutation whose cycle graph con-
tainsnþ1 cycles, which is the maximum possible number, sorting a permutationp
by transpositions comes down to, from a graph-theoretic point of view, increasing
Figure 3.1
Cycle graph of the permutation (5 41632)anditsdecomposition into three cycles
28 3 Distances between Unsigned Permutations

the number of cycles inGðpÞin as few steps as possible. The remark of Bafna and
Pevzner [30] that a transposition may increase the number of cycles by at most two
yields a lower bound on the transposition distance.
Theorem 3.3[30] For every permutationp, we havetdðpÞb
pðp?cðGðpÞÞ
2
.
This bound can be sharpened by taking the parity of cycles into account. An alter-
nating cycle is said to beoddif it has an odd number of gray (or black) arcs, andeven
otherwise. The number of odd (resp. even) cycles inGðpÞis denoted byc
oddðGðpÞÞ
(resp.c
evenðGðpÞÞ).
Theorem 3.4[30] For every permutationp, we havetdðpÞb
pðp?c oddðGðpÞÞ
2
.
3.1.2 Upper Bounds
3.1.2.1 Upper Bounds Based on Breakpoints
The ﬁrst upper bound based on the
number of breakpoints was computed by Bafna and Pevzner [30], and stated that
for allpinS
n,tdðpÞa
3
4
bpðpÞ. It is deduced from a
3
2
-approximation algorithm (see
section 3.1.5) and the lower bound of theorem 3.4. It has been outperformed by
Eriksson et al. [164].
Theorem 3.5[164] For every permutationp,
tdðpÞa
2
3
bpðpÞ

ifn<9;
2bpðp?2
3
jk
ifnb9:
8
<
:
This bound is obtained by proving that two operations, either on the permutation
or on its inverse, are su‰cient to create three adjacencies.
Figure 3.2
(a) The cycle graph of [0 5 4 1 6 3 2], and its unique decomposition into three alternating cycles ((b) two
2-cycles, and (c) a 3-cycle)
3.1 Transposition Distance 29

3.1.2.2 Upper Bounds Based on the Cycle GraphA ﬁrst straightforward upper bound
is deduced from the possibility to increase the number of cycles ofGðpÞby at least
one at each step, which corresponds to creating one adjacency at a time.
Theorem 3.6[30] For allpinS n,
tdðpÞapðp?cðGðpÞÞ:
The following upper bound is based on a
3
2
-approximation algorithm and the lower
bound of theorem 3.4.
Theorem 3.7[30] For allpinS n,
tdðpÞa
3ðpðp?c oddðGðpÞÞÞ
4
:
3.1.2.3 Upper Bounds Based on theG-Graph Labarre [240] introduced a slight vari-
ant of the graph of a permutation that proved useful for the problem studied in this
section. It is essentially the same graph, except that vertices are ordered by position.
Definition 3.4TheG-graphof a permutationpinS nis the directed graphGðpÞwith
ordered vertex setðp
1;...;p nÞand arc setfðp i;pjÞjpi¼jg.
Figure 3.3 shows an example of aG-graph. IfC¼ði
1;i2;...;i kÞis a cycle ofp,
we obtain a cycleðp
i1
;pi2
;...;p ik
Þ, which we also denote asC,inGðpÞ, and call it a
k-cycle. Thelengthof a cycle inGðpÞis thereforek.
In a fashion quite similar to the parity of cycles deﬁned in the context ofGðpÞ,a
k-cycle inGðpÞisodd(resp.even)ifkis odd (resp. even). Likewise,cðGðpÞÞdenotes the
number of cycles inGðpÞ, andc
oddðGðpÞÞ(resp.c evenðGðpÞÞdenotes the number of odd
(resp. even) cycles inGðpÞ. Labarre [240] derived an upper bound based on these cycles.
Theorem 3.8[240] For allpinS n,
tdðpÞanc
oddðGðpÞÞ:
3.1.2.4 Other Upper BoundsAn upper bound based on the length of a longest
increasing subsequence of a linear permutation was deduced by Guyer et al. [192].
Figure 3.3
TheG-graph of the permutation (4 1 6 2 5 7 3)
30 3 Distances between Unsigned Permutations

Definition 3.5Given a permutationp,asubsequenceofpis a subsetfp i1
;...;p ik
gof
nonnecessarily contiguous elements ofp, withi
1<i2<<i k. The subsequence is
increasingifp
i1
<<p ik
, and it is alongest increasing subsequenceif there is no
other increasing subsequence inpwith more elements.
Guyer et al. [192] observed that a permutation could be sorted by transpositions
by ‘‘growing’’ its longest increasing subsequence. That subsequence can always be
increased by at least 1 at each step, which yields the following upper bound.
Observation 3.1[192] For allpinS n,
tdðpÞanjLISðpÞj;
wherejLISðpÞjis the length of a longest increasing subsequence ofp.
The right-hand side of the above inequality is also known asUlam’s distance(see
Diaconis [135]), which we denote asulamðpÞ.
Benoıˆt-Gagne´and Hamel [40] proposed another view of sorting by transpositions,
in order to avoid using the cycle graph.
Definition 3.6For anypinS n, theleft codeof an elementp iis
lcðp
iÞ¼jfp jjpj>piand 1ajai1gj;
and theright codeof an elementp
iis
rcðp
iÞ¼jfp jjpj<piandiþ1ajangj:
The left (resp. right) code of a permutation is the sequence formed by the left (resp.
right) codes of its elements.
The left code of an elementp
isimply counts the number of elements that are
larger thanp
iand precede it inp, and the right code of an elementp icounts the
number of elements that are smaller thanp
iand follow it inp. For example, the per-
mutationp¼ð541632Þhas the left codelcðpÞ¼ð0;1;2;0;3;4Þand the right code
rcðpÞ¼ð4;3;0;2;1;0Þ; it can easily be seen that only the identity permutation has
ð0;0;...;0Þas both left and right codes, so the goal is to increase the number of 0s
in the left or right code of a permutation.
Definition 3.7Aplateauin a sequenceSis a subsequence of contiguous ele-
ments that have the same nonzero value. We denote asplatðSÞthe number of plateaus
inS.
Lemma 3.2[40] For anypinS n, we have
tdðpÞaminfplatðlcðpÞÞ;platðrcðpÞÞg:
3.1 Transposition Distance 31

3.1.2.5 Upper Bounds for Special Classes of PermutationsElias and Hartman [160]
proved upper bounds on the distance of three special classes of permutations.
Definition 3.8A permutationpinS nissimpleifGðpÞcontains no cycle with more
than three black arcs (the total number of arcs is at most six).
Definition 3.9A permutationpinS nis a 2-permutation(resp. 3-permutation) if all
cycles inGðpÞhave two (resp. three) black arcs.
Note that a 2-permutation (resp. 3-permutation) exists only ifpðpÞcan be divided
by 4 (resp. 3). Simple permutations were initially introduced because they are easier
to study than arbitrary permutations, due to the simpler structure of their cycle
graphs. Any permutation can be transformed into a simple permutation in linear
time (see Gog and Bader [186]), and the transformation preserves the lower bound
of theorem 3.4 on the transposition distance.
Theorem 3.9[160] For every simple permutationpthat is not a 3-permutation,
dðpÞa
pðpÞ
2

:
Theorem 3.10[160] For every 3-permutationp,
dðpÞa11
pðpÞ
24

þ
3
pðpÞ
3
mod 8

2
$%
þ1:
3.1.3 Improving Bounds Using Toric Permutations
Eriksson et al. [164] introduced a useful equivalence relation onS nwhose equiva-
lence classes are calledtoric permutations. As in the work of Hultman [214], forxin
f0;1;2;...;ng, let
x
m
¼ðxþmÞðmodnþ1Þ, and deﬁne the following operation on
extended circular permutations:
mþp
e
¼½
0
m
p1
m
p2
m
pn
m:
Two permutationsp,sinS
nare said to betorically equivalentif there exists
mð0amanÞsuch thats
e
¼mþp
e
. An equivalence class for this relation is
called atoric permutation, and is denoted byp

when it contains the permutationp.
We illustrate those concepts with the following example: letp¼ð315246Þ; then
p
e
¼½0315246, and
0þp
e
¼½0315246;
1þp
e
¼½1426350;
32 3 Distances between Unsigned Permutations

2þp
e
¼½2530461;
3þp
e
¼½3641502;
4þp
e
¼½4052613;
5þp
e
¼½5163024;
6þp
e
¼½6204135;
which yieldsp

¼fð315246Þ;ð142635Þ;ð461253Þ;ð236415Þ;
ð526134Þ;ð245163Þ;ð413562Þg, and all permutations in that set are tori-
cally equivalent.
It is easily seen that any two permutations that are torically equivalent have the
same number of breakpoints; but they have more in common, as shown by the fol-
lowing property, which is actually the main reason why toric permutations were
introduced.
Lemma 3.3[164] Any two permutations that are torically equivalent have the same
transposition distance.
This implies that any bound that is valid for a given permutation remains valid for
all permutations to which it is torically equivalent. This does not improve any bound
that is based on parameters preserved by toric permutations, such as the number of
breakpoints or the number of cycles in the cycle graph, as shown by Hultman [214].
However, any bound based on parameters that arenotpreserved by the toric equiv-
alence relation can be improved using that relation. This is, for example, the case for
the cycles of theG-graph, which helps sharpen the bound of theorem 3.11.
Theorem 3.11[240] For allp0iinS n,
tdðpÞanmax
sAp

coddðGðsÞÞ:
3.1.4 Easy Cases
This section lists some linear permutations whose transposition distance can be com-
puted in polynomial time.
Thereversed permutationw¼ðnn121Þhas transposition distance
n
2

þ1
(see Christie [115] and a simple proof by Eriksson et al. [164]).
2-permutations have a transposition distance equal ton=2 (see Christie [115]).
Permutations of the formð246n135n1Þwithneven have transposi-
tion distancen=2 (see Christie [115]).
3.1 Transposition Distance 33

Random documents with unrelated
content Scribd suggests to you:

tiesivät, että hän ei tämmöistä loukkausta kostamatta jättäisi. Mutta
salaiset juonet heitä enemmän pelottivat kuin täysi vihollisuus, ja
samassa he senkin arvasivat, että Kurjen mahtavuuden aurinko oli
laskemassa, niinpiankun hänen päämiehyytensä Pohjan miesten
seassa oli lakannut. Jos häntä tähän asti oli Ruotsin hovissakin
jotenkin suuressa arvossa pidetty, se isommaksi osaksi oli johtunut
siitä, että häntä oli katsottu ikäänkuin Pohjanperien ja Lappien
kuninkaaksi, jota ei käynyt aivan halpana alamaisena pitäminen. Jos
nyt Pouttu taikka joku muu kävisi Ruotsissa tarjoamassa yhtäläistä
alamaisuutta ilman Kurkea, niin arvattavasti Ruotsin hallitus ei ottaisi
entisen päämiehen kostotuumia suojellaksensa, ja silloin ei olisi
hätää hänen yksityisistä yrityksistänsä. Näin vanhat viisaat
arvostelivat tämän valtiollisen tapauksen valtiollisia kohtia.
Mutta Pohjan pirkkalaisissa ei ollut paljaastansa vanhoja viisaita,
vaan myöskin nuoria veitikoita, ja nämä eivät suinkaan paljon
ajatelleet valtiollisia seikkoja. Että Kurjen ukko itse muutti muuanne,
sen he kyllä mielellään näkivät; hänen kolkko katsantonsa ja ylpeä
käytöksensä ei ollut heillekään mieluinen. Mutta tämänpä he melkein
olivat unohtaa, muistaessaan hänen ainoata tytärtään, joka oli
Pohjan kuulu, Pohjan kunnia.
    Lyyli, lylyn lykkeäjä,
    Kautokengän kuluttaja,
    Hirven ahkion ajaja,
    Pohjan neito pulskeainen.
Pitikö hänenkin lähtemän pois, hänen, joka oli Pohjan poikien
ihastus ja ylpeys, "maan kuulu, veden valio"? — Vanhat viisaat
vastasivat, vaikka vastoin mieltänsä: "totta kaiketi; hän seuraa
isäänsä, niinkuin tytär ainakin" — Mutta nuoret arvelivat yhteen

ääneen: "Ei suinkaan; hän on meidän, hän on Pohjanmaan!" —- ja
totta puhuen, eivät vanhat viisaatkaan voineet tätä kieltää. Lyyli oli
ikäänkuin juurtunut Pohjanmaahan.
Kaikki tiesivät, että Lyyli itse ei tahtonut pois syntymäpaikoiltansa,
ja he tiesivät sen ohessa, että Lyyli oli itsevaltainen lapsi, Matti
Kurjen omaa jäykkää luonnetta, eikä milloinkaan tottunut muitten
tahdon alle taipumaan. Koska Luoja ei näy tehneen ainoatakaan
ihmistä niin kivikovaksi, ett'ei mitään hellää paikkaa hänen
sydämmessään ole, oli Kurjen ukollakin, varsinkin vanhalla iällänsä,
muutama heikompi puoli, ikäänkuin reikä ruosteen syömässä rauta-
asussa. Tämä heikkous oli hänen rakkautensa lapsiinsa, varsinkin
tyttäreen. Ei tarvinne muistuttaakkaan, että tämäkin rakkaus oli
itsekäs, niinkuin koko mieskin. Mutta osaksi taisivat omantunnonkin
soimaukset siitä, mitä hän äitiä vastaan oli rikkonut, tehdä hänet
hellemmäksi, jopa liiankin myöntyväiseksi tytärtä kohtaan, ja Lyyli oli
tästä syystä saanut olla ja elää varsin omin valtoinensa. Isä
enimmäkseen oli kotoa poissa, milloin Lapinmaissa käydessään,
milloin muissa tärkeissä toimissa, ja suuressa talossa, suuren
perheen keskellä oli Lyyli jo lapsuudesta asti ollut miltei ainoa haltija.
Tämä seikka oli jo aikuisin kasvattanut hänen älyänsä, mutta
samassa totuttanut hänet ohjattomaan vapauteen, johon vihdoin
vanhan Kurjenkin, kotona ollessansa, täytyi suostua. Vapauttansa ja
elämän täyttä nuoruudenriemua rakasti Lyyli enemmän kuin mitään
muuta maailmassa, ja tämä miehen luonne ilmaantui kaikissa hänen
huvituksissaankin. Taitavammin kuin hän ei kukaan osannut
purttansa ohjata Merenkurkun kuohuvissa tyrskyissä, ja tarkemmin
kuin hän ei kukaan lähettänyt nuoltansa vikkelän kärpän silmiä
kohden. Talvis-aikana oli hänen suurin huvituksensa asettaa isänsä
lahjoittama aljohirvi ahkion eteen, ja sitten niinkuin tuulen siivillä
liidellä Pohjanmaan äärettömillä nevoilla. — "Pohjan neito käy", oli

ihmisten tapana sanoa, kun hänestä vilahduksen näkivät, ja
lappalaisraukat luulivat häntä pirkkalaisten haltijattareksi, joka näille
heidän herroillensa antoi niin suurta onnea ja menestystä. Itse
Pohjan pirkkalaistenkin seassa oli monella melkein sama luulo.
Näin oli Kurjen ukko antanut tyttärensä yletä ja kasvaa
omavaltaisessa vapaudessa. Hän uljaili sydämmessään Lyylin
puhkeavasta ihanuudesta ja miettieli mielessään suurta tulevaisuutta
rakkaalle tyttärellensä. Suurta, komeata naimista hän hänelle toivoi.
Hän oli jo sitä varten muutama vuosi sitten Hämeen puolisille
tiluksilleen Vesilahdella rakennuttanut upean kartanon, josta piti
tuleman Lyylille perintö ja morsiusmyötäjäiset.
Ei ole kuitenkaan mikään niin vastenmielistä nuoren tytön kuulla
kuin toisen sille rakentamat naimistuumat, ja kun Kurjen ukko
toisinaan kuvaili tulevaista onnea ja kunniaa tyttärellensä, kuinka
hänen piti korkean miehen puolisona istua Laukon kartanossa
Vesilahdella ja tulla suuren suvun kanta-emoksi, oli tuo Lyylille
niinkuin kalman kylmyyttä, eikä hän ollenkaan voinut ymmärtää,
miksi hänen pitäisi milloinkaan naimisiin mennä ja miks'ei hänen
käynyt kaiken ikänsä tyttönä liiteleminen revontulten valaisemilla
Pohjan aukeilla tai punapurjeillansa lasketella Merenkurkun aaltojen
yli.
Mutta nyt olivat asiat yht'äkkiä saaneet vakaisemman muodon. Ei
ainoastaan Lyylin, mutta itse Kurjenkin koko perheinensä piti
muuttaa Hämeeseen. Se oli auttamaton asia. Vaivoin hillitty vihan
liekki riehui vanhan päämiehen sydämmessä. Yhteinen tympeys
vallitsi Kurjen ukon koko huonekunnassa. Itse hän valmisti
muuttoansa tulisella innolla, ikäänkuin maa olisi hänen jalkojansa
polttanut; mutta koko hänen perheensä vitkasteli, vaikka juurtunut

kuuliaisuus kuitenkin saattoi heidät isännän käskyjä noudattamaan.
Totki, tuo vanha uskollinen koira, jonka ikää ei kukaan oikein tiennyt,
veti yöt päivät surullista virttä, ikäänkuin olisi pahoja aaveita nähnyt.
Lähtöaika läheni, ja joku osa palkollisista oli jo edeltä lähtenyt
Laukkoon; toiset ottivat eronsa, kosk'ei tehnyt mielensä Pohjan
seutuja jättää. Ainoastaan viimeiset toimet olivat tehtävinä, niin
Matti Kurki saisi puhdistaa tomun jaloistansa ja lähteä pois entiseltä
vaikutusalaltaan, jota hän nyt sadatteli, — lähteä takaisin
syntymämaahansa, joka oli nähnyt hänen ensimäiset askeleensa
vallanhimon tiellä.
Mutta Lyylin piti syntymämaastaan lähteä, vieraaseen maahan,
tietymättömän tulevaisuuden maahan. Jo tämä ajatuskin tahtoi
hyydyttää hänen lämpimän verensä; mutta asia oli auttamaton. Jos
olisivat kaikki muut seikat olleet ennallaan ja vanha Kurki olisi
tahtonut ainoastaan vanhat tuumansa toteuttaa, hänen tyttärensä
epäilemättä ei olisi taipunut, — ja vaikea on sanoa, mikä vihdoin olisi
jäänyt vanhuksen päätökseksi; hän oli ennemmin tottunut tyttärensä
mukaan taipumaan kuin tytär hänen mukaansa. Mutta nyt oli itse
Lyylin tila toivoton, neuvoton. Hän tiesi, että Pohjolaiset ajoivat
Kurjen suvun pois maan-ääriltänsä. Hänelle ei voinut tulla
mieleenkään, että yleinen viha ei koskisi tytärtä samassa määrässä
kuin isääkin. Tämä luultu viha tuntui hänelle tukehduttavalta,
niinkuin raskas ukkosen pilvi, ja ahdingossaan hän melkein ikävöitsi
päästä Hämeen ilmaa hengittämään. Ja kuitenkin tämä Häme häntä
kammotti.
VITJAKKA.

Niinä viikkoina, jotka käräjistä olivat kuluneet, ei Lyyli rohjennut
käydä Pouttulassa, vaikka tuo oli hänelle tähän asti ollut niinkuin
toinen koti ja Pouttulan täti emottomalle niinkuin äidin sijassa. Tosin
Lyyli ainoastaan vaillinaisesti tiesi, mitä käräjissä oli tapahtunut,
mutta sen hän ainakin kuuli isänsä katkonaisista puheista, että
Pouttulaiset olivat hänen pahimpia vihamiehiään. Monta kertaa oli
tyttö hankkinut lähteä tätilään, mistä hän aina oli tottunut neuvoja
hakemaan. Mutta häntä oli kammottanut ajatus, että häntä
kohdeltaisiin kylmyydellä, ehkäpä vihallakin siellä, missä hänen aina
oli ollut niin erinomaisen lämmin ja hyvä olla. Hillitsemätön halu
kehoitti häntä kuitenkin sanomaan viimeiset jäähyväiset toiselle
kodilleen ja sen rakkaille asujamille. Varhain eräänä aamuna hän
istui satuloidun hevosen selässä. Matkansa kulki lounaista joenrantaa
ylöspäin, kunnes hän muutamassa uittopaikassa meni virran poikki.
Kuta etemmäksi hän kulki, sitä enemmän hänen mielensä virkistyi;
sillä kesäinen aamu on verraton lääke haihduttamaan kaikkia
mielialoja. Melkein tavallinen ilonsa hohti Lyylin kauniista kasvoista,
hänen astuessaan Pouttulan pirttiin.
— Käyn hirveäni hakemassa, missä lieneekään, kun ei ole moneen
aikaan nähty, ei kuultu. Täytyy pitää se tästä lähtien kytkyessä,
muutoin karkaa takaisin Pohjanmaalle. — Etkö tahtoisi toki minua
auttaa, Vitjakka?
Pouttulan pirtissä istui koko perhe eineellä, isäntä, tuo uusi
päämies Viljakka Pouttu, ja emäntänsä poikineen. Vanhin poika,
Vitjakka, oli pitkä, pulskea nuorukainen, jolla jo oli suuri maine
lapinkävijäin seassa rohkeudestaan ja miehuudestaan kaikissa
vaarallisissa tiloissa sekä talvimatkoilla autioissa erämaissa että
kesäretkillä, Pohjanlahden ja Raumanmeren aavoilla laineilla. Hän oli

syntyessä saanut nimen "Vitjakka" ja äitinsä oli jo silloin ripustanut
vahvat hopeavitjat hänen kaulaansa ikäänkuin miehuuden merkiksi.
Mielihyvän loiste, joka oli tytön tullessa leimahtanut Vitjakan
silmissä, katosi kohta, kun hän tervehdyssanat kuuli. — Näinkö
jäähyväiset sanottiin Pohjanmaalle — tuttaville?
— Elä huoli kytkyttä laittaa! sanoi vihdoin Vitjakka, — hirven
emäntä tulee ritarilliseksi rouvaksi ja hirvi itse ritarilliseksi hirveksi.
Mikä sen sitten on ollessa! Pohjan laitumilla ei kasva kelvollista
ruohoa niin korkea-arvoiselle elukalle.
Tyttö oli istuutunut lavitsalle. Hän lausui levollisella vaikka
hiljaisella äänellä:
— Teet hirvelleni väärin, — ja ehkä hirven emännällekin.
Molemmat pannaan kytkyeen ja molemmille on kytkyt yhtä outo.
Mutta toista ei vihata missään; sillä on maailma vihanta joka maassa
ja syytä on pelätä, että se rikkoo kytkyensä palatakseen
syntymäpaikoillensa. Toinen taas ajetaan maanpakolaisuuteen
syntymäkedoiltansa.
— Sinutko maanpakolaisuuteen, Lyyli! huusi Vitjakka riehahtaen.
— Kukapa sinusta on eroa pyytänyt? Etkö olisi voinut tänne jäädä,
antaen isäsi lähteä? — tämän julman isän, joka tappoi tyttärensä
äidin, tappoi sinun äitisi, Lyyli! — Etkö olisi voinut jäädä tänne, tänne
syntymätaloosi, jota olet lapsuudestasi tähän saakka hallinnut? Etkö
olisi voinut, kun olisit tahtonut? Sillä ethän olekaan muiden tyttöjen
tapainen: sinä olet syntynyt käskemään ja itse Kurjen ukko on
pääsemättömissä, kun sinä jotakin tahdot. Mutta et varmaankaan
tahtonut. Voi kaikkien meidän riemua, jos olisit tahtonut!

Vaaleana, kalmankalpeana istui Lyyli kuin jäätynyt, ja hänen
sydämmensä oli pakahtua. Hän oli nyt ensi kerran suorin sanoin
kuullut äitinsä surman mainittavan, ja muistaessaan himmeitä
huhuja, joita hän ei tähän asti ollut ymmärtänyt, hän ei enää voinut
epäillä, että tässä joku hirveä totuus oli salattuna. Maailma oli
yht'äkkiä käynyt hänelle autiommaksi kuin Lapin lumiset aukeat.
Tyttö oli vieraantunut ainoastakin turvastaan, mikä hänellä oli, —
vieraantunut omasta isästänsä, murhaajasta.
Mutta kuka se oli, joka lämpimällä kädellä pyhkeili neidon
kylmänhikistä otsaa? — jonka rintaa vasten neito vaipui, sulaen
kyynelvirtoihin? — Se oli Vitjakka Pouttu. Lyyli taas nousi; mutta
kuinka muuttuneena! Hänen uljas uskalluksensa, joka ei tarvinnut
muihin turvata, oli nyt taittunut, notkistunut. Hän oli sortuneena
kovan kohtalon alla, mutta samassa oli hän löytänyt ketä vastaan
nojata. Hän oli nyt nainen, toisen turviin pakeneva, heikko, nöyrä ja
taipuvainen.
— Mitä minun on tehtävä? oli hänen ensimäinen kysymyksensä.
— Jää minulle, vastasi Vitjakka; — tämä käsi sinua holhoo ja
puolustaa. — Nuorukaisen silmät välkkyivät miehuuden voimasta.
Mutta vanha Pouttu pudisteli päätänsä. — Saammehan mennä
kuulustamaan, mitä Matti Kurjella on siihen sanomista. Minä en
hyvää vastausta odota. Ja jos niin on, niin tytär seuraa isäänsä. Ota
hänet sitten, poika, millä keinoin voit. Mutta varkain emme häntä
täällä pidä.
Se oli sana, jota ei kenenkään käynyt vastustaminen. Illan tullessa
oli Lyyli taas kodissansa, ja seuraavana aamuna kävi vanha Pouttu
poikansa kanssa Kurjen talossa, pyytämässä neitoa miehelään.

Vanha päämies vastasi pilkalla ja ylenkatseella. Hänen ei muka
sopinut naittaa tytärtänsä alamaistensa pariin, mutta lupasi kuitenkin
heidän mielikseen toimittaa niin, että Lyyli vasta, jonkun mahtavan
ritarin rouvana, palaisi Pohjanmaalle, hallitsemaan ja vallitsemaan
perintöoikeutensa nojalla.
Vanha Pouttu muistutti levollisesti, että vanhuus oli tehnyt entisen
toverin pään heikoksi, niin ett'ei hän osannut eroittaa mennyttä
tulevaisesta, eikä mielikuviansa olevaisista oloista. Ritarillisella
herruudella oli oleva huono menestys Pohjanmaalla, vaikka sitä
Lyylinkin kädellä käytettäisiin. Pohjanmiehet eivät olleet unohtaneet,
millä lailla heidän isänsä olivat ennen naisia kosineet. Ja mitä silloin
oli tapahtuva Kurjen ukolle ja hänen ritareillensa, sen hän oli saava
lukea omaksi syykseen.
— Kaitse tyystin tytärtäsi! huusi Vitjakka, ratsunsa selkään
hypätessään; — vaikka hänet rautapaitasikin alle kätkisit, minä hänet
sieltäkin löydän. Pysy valveilla vuoden pisimpänä yönä!
Sininen silkkivyö viittasi luhdin akkunasta jäähyväiset
poismenijälle. Hän ajoi ratsunsa siitä alitse, ja vyö laskeutui alas
hänen olkapäilleen. Sanaa virkkamatta ajoivat Pouttulaiset kotiansa.
VUODEN PISIN YÖ.
Joulun lähestyessä asteli Matti Kurki levottomin askelin juhlasalinsa
permannolla Laukon kartanossa. Hänen silmänsä olivat vähän
kadottaneet entistä terävyyttänsä ja askelissa oli vähäinen, tuskin
havaittava horjunta; mutta kasvot olivat melkein kamalat.
Mielikarvaus, ikävyys ja kostonhimo kalvoivat entisen
Pirkkalaispäämiehen sydäntä. Hän katseli väliin huonetta, joka oli

pitoja varten koristettu, pöydät peitettyinä hienoilla englannin
veroilla, lavitsat ja penkit varustettuina pehmeillä tyynyillä ja
villavaipoilla. Mutta tätä katseltuansa hän vaipui omiin ajatuksiinsa ja
ärjähti toisinaan itseksensä, johon Totki, joka uskollisesti seurasi
hänen jälkiänsä, vastasi lyhyellä haukahduksella.
Lavanalustan puolella istui Lyyli työnsä ääressä. Palvelija näytti
valkeata leimuavalla soihdulla, ja lisäksi paloi viereisellä pöydällä
kynttiläkin semmoinen, jonka käyttämisen uuden uskon kirkolliset
menot olivat Suomenmaahan tuoneet. Lyyli oli kalpeampi kuin
ennen, iloinen lapsellisuus oli kasvoista hävinnyt; suru ja kaipaus
asui silmissä.
— Mitä sinä teet? kysyi Kurki pysähtyen. Hänen äänessään ei enää
ollut havaittavana entinen lempeys tytärtänsä kohtaan.
— Hää-ohjaksia sulholleni, vastasi tytär vakavasti.
— Se on oikein, jatkoi isä leppeämmin; tänä ehtoona jo tulee
Harald ritarinensa Birger Jaarlin linnasta. Huomispäivän pidämme
iloa täällä ja aikaisin ylihuomen-aamuna ajamme juhlallisessa
häämenossa Sastamalan [tämä oli Karkun pitäjän sen aikuinen nimi]
kirkolle vihkiäisiin. Sitten odottavat komeat tuliaiset nuorta
linnanrouvaa Hämeenlinnassa. Et taida tietää, että koko Pohja on
laskettu Haraldin läänin alle. Harald on mahtavin ritari koko
Suomenmaassa. Ruotsin marskin omaa sukua — —
— En tunne ritari Haraldia, enkä tahdo häntä tuntea, sanoi neito
punastuen mielipahasta. Olen jo sen usein sanonut teille, olen toisen
oma.

Kurjen ukko polkasi jalkaansa permantoon, niin että rautarenkaat
helisivät ja salin laki kajahti. Palvelija hämmästyksissänsä päästi
soihdun maahan, johon se sammuneena jäi karrestansa suitsemaan.
— Jos et käskyäni noudata, lähetän sinut vetten ja vuorten taa
Saksan synkimpään naisluostariin. Olet jo liian kauan
kärsivällisyyttäni koetellut. Sinä olet äitisi kaltainen, mutta minäkin
olen se sama Matti Kurki mikä ennen. Tiedä se, että äitisi on
verellänsä maksanut ynseytensä.
— Minä tiedän sen, enkä pelkää, vastasi Lyyli jäisellä äänellä,
lähtien ulos salista. — Sanomaton viha valtasi vanhuksen. Hän
istuutui lavitsalle uupuneena. Hämmästyen hän tunsi, että entinen
jäntevyys oli jäsenistä poissa, että ikä oli kuluttanut hänen voimansa.
Mutta nyt kuului ulkoa hevosten astumista. Ritari Harald
seurueinensa oli tullut. Kurjen ukko virkosi uupumuksestaan ja
vieraat johdatettiin juhlasaliin pitkän peräpöydän ääreen. Se oli
vahva roteva mies tämä aiottu Kurjen vävy, ei enää aivan nuori,
täydessä ritarin asussa, kopea käytökseltään ja katsannoltaan.
Hänen seurassansa oli useita ritareita ja asemiehiä. Muutamat näistä
seuraajista olivat suomalaista sukua ja näitä Harald varsinkin kielen
vuoksi tarvitsi; sillä itse hän oli äskettäin tullut Ruotsista eikä
osannut meidän maan kieltä.
Knaapit ulkona riisuivat herrojensa hevosia ja saivat sitten hekin
sijansa juhlasalissa, vaikka oven puolella. Riemu oli pian ylinnä
vierasten kesken; sillä olut suurissa hopeajalkaisissa sarvissa kulki
ahkerasti kädestä käteen ja väkevää kryydittyä saksan viinaa
hopeisessa maljassa oli jokaiselle tarjona, jos olueen ruvettiin
kyllästymään. Riemu vaikeni vaikenemistaan. Matkasta väsyneet ja
juomien voittamat miehet olivat oijenneet mikä mihinkin.

Sydänyön aikana syntyi äkkiä meteli makaavien joukossa.
Knaapeista oli yksi ollut vahtina ja toi nyt hätäisen sanoman, että
suuri joukko kummallisia eläimiä, joiden päät olivat pensailla
koristetut, läheni järven jäältä kartanoa, ja että kunkin vedettävänä
oli reki täynnänsä miehiä, jotka eivät suinkaan rauhallisessa
aikomuksessa näin tulleet. Ritarit olivat pian pystyssä ja pihalla,
missä hämmästyen katselivat tulijoita, joiden reet kulkivat kuin
yhdellä jalaksella ja joiden hevosia ajettiin kuin yhdellä ohjaksella.
Kohtapa havaittiin, että ensimäisen sanan tuoja oli liikoja nähnyt;
sillä rekiä oli ainoastaan kymmenkunta, ja kussakin vain yksi mies.
Mutta kammottihan kuitenkin tämä outo näky, — nämä hennot ja
kepeät, pensaspäiset elukat kummallisine ajokaluinensa, — ja moni
ritareista teki ristinmerkin, luullen tässä alkavan taistelun paholaisten
kanssa.
Ainoastaan Matti Kurki tunsi tulijat lappalaisiksi, vaikka hänkin
kummasteli, mitä asiata nämä Laukon kartanossa kävivät. Hän meni
siis heitä vastaan ja kyseli tylyllä äänellä, ketä he hakivat, näin
yösydännä tullessansa. Kohta nousi ensimäisestä ahkiosta lyhytläntä
vanhus ja laski syvästi kumartaen kihtelyksen näädän-nahkoja
kysyjän jalkain juureen. Tämä lahja lepytti vanhaa lapinkävijäin
päämiestä, joka nyt ystävällisemmin käski tulijain johdattaa peuransa
pihaan ja itse astua katon alle. Mutta vanha lappalainen sanoi
itsensä mahdottomaksi oleskelemaan katon alla siinä talossa, missä
kuninkaat ja ylimykset ilojansa viettivät, vaan pyysi kuitenkin
saadaksensa alhaisilla lahjoillansa kunnioittaa sitä suurta
linnanhaltijaa, joka nyt oli hänen ja koko Lapinkansan herraksi
asetettu. Ritari Harald, jolle tämä lause selitettiin, veti suunsa
sääliväiseen hymyyn, mutta muutti muotonsa nähdessään ne kalliit
nahkat, joita hänen eteensä ladottiin; — ja kuullessansa, että tämän
joukon matka ei tarkoittanut muuta kuin kunnianosoitusta hänelle,

hän jalosti suvaitsi luvata näille raukoille korkean suojeluksensa.
Sitten ritarit taas palasivat oluenjuontiinsa. Ainoastaan Kurjen ukko
jäi hetken ajaksi vanhan lappalaisen puheille, onkiakseen häneltä
kuulumisia Pohjan pirkkalaisista. Niistä ei kuitenkaan lappalainen
sanonut paljon tietävänsä. Ainoastaan kaukaisena huhuna oli hän
kuullut, että riita ja eripuraisuus oli ylinnä lapinkävijäin seassa, ja
että he tältä riidaltansa eivät tänä talvena malta käydä veroansa
kokoilemassa lappalaisilta. Tämä sanoma ilahdutti Kurkea enemmän
kuin lappalaisten tuomat lahjat ja hän käski tuoda matkalaisille
vaahtoavaista olutta, ennenkun taas lähtisivät salomaihinsa
palaamaan. Se oli Lyyli, joka suurissa haarikoissa tarjosi vieraille
virvoittavaa mallasmehua, ja Lapin vanhus osoitti tarjoojalle ja
tarjottavalle kaikkea kunniaa, tyhjentäen haarikan pohjaan asti.
Mutta mikä oli tuo kiiltävä esine, jonka hän kenenkään
huomaamatta päästi haarikan pohjaan, antaessaan astian tyhjänä
takaisin tarjoojalle? Ja mikä leimaus loisti Lyylin surullisissa silmissä?
— Se oli lahja, jota ei olisi lappalaisen kädestä osannut odottaa,
lahja luultavasti neidon hääpukuun aiottu, — vahvat hopeiset
ritarivitjat.
— Jos joskus tarvitsette hevostanne syöttää Kauraharjun
kukkulalla, niin minä teidän hyvyytenne tahdon palkita, korkea neito!
lausui lappalainen jäähyväisiksi — ja pian oli taas koko seurue
paluumatkalla.
Mutta juhlasalissa oli taas ilo alkanut ja kesti koko päivän. Ritarit,
asemiehet, knaapit ja muut palvelijat tyhjentelivät kilpaa Laukon
oluttynnöreitä, ja itse isäntäkin oli paremmalla tuulella kuin moneen
aikaan. Hän oli jo kohta pääsemässä toivonsa perille tyttärensä
naittamisasiassa; hänen kostonhimonsa hehkui hekkumallisesti

hänen ajatellessansa Pohjan miesten nykyistä eripuraisuutta, josta
vanha lappalainen oli tiennyt jutella, ja vielä enemmän lupasi lähin
tulevaisuus tyydyttää hänen mielensä tuimuutta. Vanhan päämiehen
synkät kasvot selkenivät, kun Lyyli täydessä juhlapuvussa astui
vähäksi aikaa vierasten joukkoon, täyttäen kohteliaasti emännän
velvollisuudet.
— Minä juon teidän terveeksenne, korkea neito, lausui Harald
ritari, tyhjentäen yhdellä henkäyksellä sarvellisen olutta. — Se on
oikein, että olette pukeunut ritarillisiin vitjoihin; sillä mahtavan ritarin
morsiamen sopii ritarillisissa pukimissa käydä. Mutta koska teillä on
vitjat ennestään, annan minä teille toisen kannukseni. — Näin
sanoen hän riisui kannuksen jalastansa.
Lyylin poskipäihin olivat kaikki ruusut palanneet.
— Se on totta, hän lausui ylevästi, vitjain omistaja ansaitsee kyllä
kantaa ritarillisen kannuksenkin. Tämän omistajan puolesta minä
teille, korkea ritari, lahjoitan kiistakintaan. — Näin sanoessaan neito
päästi rautakiskoilla päällystetyn kintaan ritarin jalkain juureen.
Sumu hetkeksi lensi Kurjen kasvojen yli, huomatessaan
hopeavitjat tyttärensä kaulassa. Joku hämärä muisto oli riehahtanut
hänen mieleensä. Mutta kaikki selkeni, kun Harald naurusuin nosti
kintaan, lausuen:
— Siinä kiistassa toivon molempien tulevan voitetuiksi. Minä jo
olen voitettu kauneuden voimalla.
Ritarin seuraajat, joissa mallasmehu jo oli tehnyt vaikutuksensa,
lisäsivät näihin sanoihin leikillisiä selityksiänsä, jotka pian ajoivat
Lyylin pakoon juhlasalista.

Illan tullessa nousi naittajan ja ylkämiehen välillä puhe
myötäjäisistä ja huomenlahjoista. Kurjen ukosta oli ensimmältä kovin
outoa, että Harald ensiksi aikoi viedä tyttären ilman hinnatta ja vielä
päälliseksi vaati tavaroita morsiamen myötä. Päinvastoin oli hänen
nuoruudessansa ollut Suomen miehillä tapana, että kosija maksoi
morsiamen sukulaisille kalliin hinnan vietävästään, ell'ei nähnyt
soveliaammaksi ottaa naistansa väkisin ja sitten pitää miekalla
puoltaan morsiamen sukua vastaan. Että kosija nyt tahtoi
myötäjäisiä, oli ikäänkuin halveksimista, ja vähällä oli, ett'ei koko
kauppa olisi mennyt rikki. Kuitenkin, kun vanhukselle selitettiin, että
myötäjäiset olivat annettavat morsiamen omaksi eikä ylkämiehen, ja
että jälkimäisen piti samoin antaa puolisolleen samanarvoinen
huomenlahja maatiluksina tai muuna omaisuutena, niin Kurki
myöntyi ja lupasi tuoda semmoiset aarteet, joita harva Ruotsin ritari
vielä oli morsiamensa kanssa saanut myötäjäisiksi. Nämä aarteet hän
tahtoi nyt kaikkien ritarien läsnäollessa jättää vävymiehen käsiin ja
häneltä taas ottaa juhlallisen vakuutuksen huomenlahjasta. Hän
käski vierasten viljellä olutvaroja ahkerasti ja lähti itse valitsemaan
soveliaita kalleuksia niistä aarteista, jotka Laukon kellarissa
säilytettiin.
Vuoden pisin yö oli jo ruvennut hämärtämään, ja aikaisin
aamupuolella yötä piti hääseurueen lähteä Laukosta Sastamalaan.
Knaapit ja palvelijat valmistelivat herrojensa hevosia juhlamatkan
komeutta varten.
— Kuka tuo pitkä ritari on, joka sivutsemme kävi; se ei ole
meikäläisiä? puhui yksi knaapeista toiselle, heidän askaroidessaan
pihalla hevostoimissa.

— Ritari, eikä meikäläisiä! vastasi toinen — puhutpa joutavia!
Luuletko Saksassa olevasi, vai missä? Eihän Suomen miehissä ole
ritareita, ei sukuakaan, ell'et ritariksi sano sellaista tervaskantoa kuin
tuo vanha Kurki on. Mutta sinäpä aina loruja latelet.
— Sanon kuin sanonkin, että se oli ritari, koska näin
kultakannuksenkin hänen kantapäässään. Ja eikö hän nyt tuolla
toisella puolella pihaa, sininen vyö hartioillaan, valjasta reen eteen
yhtäläistä kummallista elukkaa kuin minkä viime yönä näimme,
silloin kun nuo linnunkotolaiset, tai mitä lienevät olleet, kävivät —?
— Ja kun sinä peloissasi luulit koko sotajoukon paholaisia
karkaavan päällemme ja vähissä hengin tulit turmelemaan hyvää
yöuntamme. Sopisihan sinun nytkin juosta tärkeän tietosi kanssa
ritarien puheille. Ha, ha, ha! Tekisi mieleni nähdä, kuinka palaisit
uudestakastettuna oluella.
Toinen knaappi, jolle nämä pilkalliset sanat lausuttiin, oli vetää
miekkansa tupesta vastaukseksi, kun samassa juhlasalin ukset
ulvahtivat ja talonisäntä soihtu kädessä astui ulos, käyden pihan
poikki vahvan rautaoven luo, joka vei Laukon kellariin. Totki, joka
seurasi hänen jälkiään, ärähti pahasti pihalle tullessa, mutta vaikeni
kohta isännän käskystä. Totutetun tapansa mukaan se jäi
ulkopuolelle oven vartijaksi, kun Kurki itse kellariin astui.
Tämä Laukon kellari oli alkuansa luonnollinen vuorenluola, joka
pienestä suustaan ulottui syvälle maan uumeniin. Jo siihen aikaan
kun ensimäinen siirteleväinen lappalainen oli tälle paikalle laukkunsa
laskenut, lausuen, kuten tarina mainitsee: "Tähän lasken laukkuni;
tämä Laukko olkoon", oli tätä avaraa rotkoa ruvettu käyttämään
kellarina, johon lappalaiset kesän aikana laskivat kalansaaliinsa
säilytettäväksi. Mutta kalliimpia tavaroita oli Matti Kurki tiennyt siihen

koota ja vahva rautainen ovi telkeinensä, lukkoinensa oli nyt luolan
suuhun sovitettu. Jyrkät portaat veivät kohta ovelta alas avaraan
kehään, jonka perällä pimeä aukko johdatti teihin tietymättömiin.
Mutta sivupuolella tästä yleni toinen yhtä avara kellari, johon alisesta
kehästä päästiin portaita myöten ikäänkuin lavalle. Siinä Kurjen ukko
säilytti kaikki ne kalliit kalut, mitkä hän koko ikänsä kuluessa oli
koonnut, milloin sotaretkillänsä, milloin veron- ja kaupankäynnillä
pirkkalais-aikanansa. Kaikki muistojen haahmot astuskelivat tässä
vanhuksen silmien eteen, mitkä hymyhuulin hänelle muistuttaen
entisiä iloja ja maineita, mitkä taas irvihampain soimaten häntä
monesta julmasta ja tunnottomasta teosta. Kullat ja hopeat, vaatteet
ja kalliit nahat, aseet ja sotakoristukset, mitkä seinissä riippuivat, —
kaikilla oli jotakin juttelemista vanhalle uroolle lohdutukseksi tai
kiusaksi, hänen kuluneen elämänsä tarinasta.
Soihdun liekki valaisi naisen vaatepartta, joka riippui
perimmäisessä sopessa, ikäänkuin kätkettynä. Hunnussa näkyi vielä
ruskeita verentahroja ja hame oli revitty ja rikki leikattu. Toinenkin
huntu riippui siinä vieressä, melkein yhtäläinen, ja sekin verellä
soaistu! — Kurjen synkimmät muistot astuivat tässä hänen eteensä
ja hänen vanhaa syyllistä sydäntänsä tuimasti pöyristytti. Hänestä oli
ikäänkuin molemmat hänen naisensa olisivat siinä seisoneet
surmapuvussansa, odotellen sitä aikaa, milloin täydellinen kosto
antaisi heille rauhaa Tuonen tyynissä tuvissa.
— Olenko koskaan naisia pelännyt? hän murahti, vihaisesti
kääntäen selkänsä vainajien luultuja haahmoja kohden. Mutta kuinka
hän yrittikin karaista sydäntänsä ylenkatsomaan vainajien vihaa,
täytyi hänen kuitenkin taas palauttaa silmänsä heidän puoleensa.
Hän oli selvästi kuullut kahinan jonkinmoisen, ja riehaantuneessa
mielessään hän oli tuntevinansa, ikäänkuin haahmot olisivat

lähteneet häntä takaa ajamaan. Kuitenkin veriset hunnut yhä olivat
asemillaan. Mutta luultavasti Totkikin yhtäläisiä kummia kuuli tai
näki, koska häneltä kuului outo ärinä, missä oven edessä vartioi.
Tuskin oli Kurki ennättänyt ruveta tätä uutta kummaa
kuuntelemaan, kun Totki viskattiin voimakkaasti kellarin portaita
alas, ovi paiskattiin kiinni ja telkeet lukkoinensa pantiin eteen. Kurki
riensi soihtu kädessä aliseen kellariin ja siitä portaita ylös ovea
vastaan, jota tömistytti, kunnes havaitsi sen olevan täysissä
telkeissä. Raosta oven ja pielen välistä loisti palo. Se oli juhlasali,
joka oli sytytetty. Kauhea viha vimmasi Kurjen päätä. Olivatko hänen
ruotsalaiset vieraansa hänet pettäneet, ryöstäneet hänen tyttärensä,
niinkuin Kurjen omassa nuoruudessa oli ollut tapana, ja teljenneet
hänet itsensä vuoren luolaan? Tämä ajatus pani hänen verensä
kuohumaan. Oven tukevuuden hän kyllä tunsi ja tiesi siis
poispääsönsä mahdottomaksi.
Mutta Laukon pihassa oli knaappien toraa vielä jatkettu, kunnes
molemmat tulivat siihen vakuutukseen, että se outo mies, jonka
olivat nähneet hämärässä askaroivan, oli vain joku Matti Kurjen
palvelijoita. Oli jo niin pimeä, ett'eivät he voineet mitään eroittaa.
Yht'äkkiä kuului kauhea ärinä, ikäänkuin koiran, joka oli
kuristumaisillaan. Samassa rautaovi kuului rämähtävän kiinni.
Molemmat knaapit juoksivat lentämällä herrojensa luo näitä kummia
ilmoittamaan. Saliin tultuaan näkivät he tulen syttyneen useassa
paikassa. Ritarit olivat jättäneet juominkinsa ja kiiruhtaneet paloa
pakoon pihalle. Haettiin Laukon isäntää; — hän oli poissa. Poissa oli
Lyylikin, morsian, jonka tähden vieraat olivat tulleet. Ritarit eivät
tienneet mitä ajatella näin kummallisesta seikasta. Oliko Kurjen ukko
ollut naimisehtoihin tyytymätön ja lähtenyt tyttärensä kanssa pakoon

— ja minne pakoon? — Näillä arvoituksilla päätänsä vaivaten seisoi
Harald miehinensä tulipalon loistaessa Laukon pihalla.
Mutta jäätä myöten pohjoiseen kulki vihurina hirven vetämä reki,
kaksi henkeä nahkapeittojen välissä. Se oli Pohjan piltti, joka
"vuoden pisimpänä yönä" vei morsiamensa appelasta Pohjan aukeille
rämeille takaisin. Se oli Lyylin hirvi, joka ilosta päristen palasi
syntymämailleen.
(Yrjö Koskinen: Pohjan piltti.)
PIKAKUVA PIISPA MAUNU I:stä.
Vähän matkaa satamapaikasta sorjan kuusimetsän takana oli
kunnaan rinteelle rakennettu Kuusiston hovi, jonka Maunu piispa oli
omilla varoillansa ostanut, mutta antanut lahjaksi Pyhälle Henrikille,
se on Turun uudelle tuomiokirkolle ja Suomen piispanistuimelle.
Tämän hovin asuinhuoneet eivät tähän aikaan vielä olleet mitään
loistavia, vaikka monessa kohden tarpeen mukaisia. Avara sali eli
pirtti, joka pidettiin palvelijain olinpaikkana sekä kokoussalina
juhlatiloissa, oli vahvoista honkahirsistä salvettu eri kehänä, josta ovi
vei korkeaan esikkoon eli porstuaan. Toisella puolella porstuata oli
jotenkin yhtäläinen kehä, mutta sivuseinällä jaettu neljään
kammioon, joissa arvokkaammat vieraat saivat yösijansa. Piispan
omat huoneet olivat eri kehässä, jonka etuseinä pisti vähän matkaa
sisään muiden kehien väliseen porstuaan, jotta tämä salvos käänsi
päätynsä porstuan perään ja siitä ulkoni rannan puolelle. Kaikki
nämä kolme kehää muodostivat yhdessä ikäänkuin linnun, jonka
vartalo oli tuo keskellä oleva porstua, johon piispan huoneet liittyivät

nokkana ja muut salvokset siipinä. Porstuanperäinen rakennus oli
oikeastaan tehty kahteen kerrokseen, josta alinen ja matalampi oli
hovin kellari, missä oluet ja viinivarat talletettiin maanalaisessa
holvissa. Ainoastaan ylinen kerros oli asuttavana ja muutamat
porrasasteet veivät porstuasta pirtin seinustaa myöten ylös tämän
ylisen kerroksen tasalle, missä vähäinen käsipuilla varustettu sola oli
oven edustana. Ovesta sisään mentyä tultiin ensin isompaan
huoneeseen, jonka perällä oli soukka kammio salvoksen
ulommaisessa päädyssä. Nämä huoneet olivat varustetut pienillä
lyijynliitteisillä lasi-ikkunoilla. Mutta muissa asuinhuoneissa oli
ainoastaan tavalliset laudalla tai ohuella nahalla peitetyt ikkunat.
Tämmöisessä asunnossa asui Maunu-piispa, kun virkatoimet eivät
vaatineet häntä olemaan Räntämäellä tai Turussa; mutta
jälkipiispoillensa hän oli alkanut rakennuttaa komeampaa ja
vahvempaa kivistä asumusta, jonka perustukset ja aliset
kivikerrokset jo nähtiin vähän matkan päässä, itse mäen kukkulalla.
Tämän nousevan linnan peruskivillä nähtiin vanha piispa usein
istuvan yksin ajatuksissansa, hengessänsä miettien isänmaansa ja
kansansa tulevaisuutta ja sivistyksen voitontoiveita tässä syrjäisessä
maassa. Silloin hän tavallisesti äkkiä nousi seisomaan korkeimman
muurikiven päälle, ikäänkuin avarampaa näköalaa etsien
tulevaisuuden aavalla merellä, ja antoi silmänsä kulkea niemien
nenitse salmien ja selkien yli. Hänen koko huolenpitonsa ja
rakkautensa tarkoitti suomalaisten parasta. Heitä, omia
kansalaisiaan, hän suositteli, eikä siinä pitänyt suurta lukua Ruotsin
vallasta, eikä aina kirkonkaan eduista. Antoipa hän kerran
hämäläisillekin anteeksi neljännen nahan omista
piispansaatavistansa siitä ainoasta syystä, että nämä olivat kärsineet
venäläisten hävityksestä. Hänen alinomainen lauseensa oli, että
tämä kansa on leppeydellä ja hellyydellä johdatettava kristillisyyteen,

ja että tässä maassa ei vielä sovi vaatia täydellistä katoolista
vanhurskautta. Mutta erittäin hän pelkäsi ja kammoi ruotsinväen
muuttamista tähän maahan; siitä hän pelkäsi tämän kansan
sortuvan. Hän oli salaisesti Ruotsin vallan vastustaja, ja paavillisen
istuimen läheisyydessä oli hänellä puolustajia, jotka ajoivat hänen
asioitaan. Hän oli Roomassa tehnyt muistutuksia Liivin papiston ja
ritariston menettelystä sen maan asukkaita kohtaan. Mutta
tulevaisuus oli hänelle sumujen ja hämärien peitossa, joissa
ainoastaan ihmisen omat toiveet kangastuvat, ja piispa Maunu
istuutui taas lepäämään, jättäen isänmaansa asiat kaikkivaltiaan
huomaan.
Tänä aamuna varhain näemme taaskin vanhan piispan kävelevän
linnan asemilla, ei kuitenkaan yksinänsä, vaan nuoren nepaimensa,
Lauri nimisen koululaisen eli "scholarin" seurassa. Piispa itse oli
vanhahko harmaapäinen mies, jonka pienet siniset silmät leppeästi
pilkistelivät siniharmaan patalakin alta. Musta kauhtana, jonka
rintaan valkoinen risti oli ommeltu, välähteli hartioilta alas hänen
vartensa ympäri ja hänen kädessään oli pitkä valkoiseksi maalattu
sauva, jota hän piteli melkein keskeltä, nojaten sillä askeleitansa,
jotka kuitenkin olivat jokseenkin vilkkaat ja voimalliset. Hänen
nepaimensa oli 18-vuotias nuorukainen, jonka keskeltä jaetut
keltaiset hapset käherinä vierivät olkapäille. Hänen pukunsa oli
muutoin melkein yhtäläinen kuin sedänkin, ilmaisten, että
hengellinen sääty oli hänelle elämäntoimeksi aiottu.
— Omatuntoni minua vaivaa, virkkoi piispa alakuloisesti, kun olen
tähän linnan rakentamiseen ryhtynyt, ennenkun Pyhän Henrikin
temppeli Unikankarilla on valmiina. Suokoon Jumala ja Pyhä Henrikki
laupiaasti, ett'ei tätä tekoani luettaisi minulle kuolemansynniksi.

— Isä, virkkoi nuorukainen nöyrästi, eikö Jumala ja kaikki Pyhät
tunne sydämmenne puhdasta tarkoitusta?
— Siitäpä tarkoituksesta, vastasi piispa, päätänsä pudistaen, olen
juuri itsekin epätietoinen. Tämän linnan olen tosin Pyhälle Henrikille
aikonut, hänen seuraajoillensa ja maalliselle tavaralleen
turvapaikaksi. Mutta tällä lahjallani on toinenkin salainen tarkoitus,
jota sieluni vapisee ajatellakaan. Minä tahtoisin lepyttää Pyhän
Henrikin vihaa murhaajaansa kohtaan, — minä tahtoisin Pyhän
Henrikkimme omilla esirukouksilla lunastaa Lallin sielun helvetistä.
Minä olen aikonut — Jumala minua armahtakoon — asettaa tässä
syrjäisessä paikassa jokapäiväiset messut Lallin sielua varten. — —
— Lallia varten sielumessuja? virkkoi säikähtyen nuorukainen; Lalli
oli murhamies, marttyyrin surmaaja!
— Hän oli syntinen niinkuin me kaikki, vastasi leppeällä
vakavuudella vanhus. — Kaikki olemme synnillämme Kristuksen
surmanneet ristin hirsipuussa. — — Eikä Lallikaan ollut muuta kuin
ihminen: hän oli omaa vertasi, — minun ja sinun sukua. — Hänen
sydämmensä tosin oli sokea, mutta juuri siitä syystä lienee syntinsä
vähempi, ja mekin kaikki olisimme hänenä saattaneet saman tehdä.
Vieras valta ja vieras usko oli kaksi asiaa, jota eivät esi-isämme
silloin vielä eduksensa ymmärtäneet. —
— Jumala sen nähköön, lausui hän juhlallisella äänellä, syvästi
huoahtaen, — Jumala nähköön, kuinka näitä suomalaisia kansoja on
käännetty rakkauden uskoon. Liiviläiset ovat tässä kaupassa kaiken
maallisen onnensa kadottaneet, virolaisten on melkein samoin
käynyt ja täällä Suomessa ajettiin Hämeen miehet merensyrjästä
takamaihinsa. Ovatko nämä rakkauden töitä? Tahdotaanko sillä
tavoin perustaa rakkauden oppi sydämmiin? Tämä kansa on harras

ja sydämmellinen, siveä, vakava ja uskollinen; mutta hellästi sitä on
kohteleminen, muutoin se muuttuu julmaksi ja taipumattomaksi.
Tätä pitäisi valtiasten muistaman. Mutta — — oi, milloinka on heikon
hätähuuto liikuttanut mahtavan sydäntä!
(Yrjö Koskinen: Pohjan piltti.)
PIISPA HEMMINGIN AIKOJA

HIRMUKUOLEMA.
Turun tuomiokirkon sakariston ovi aukeni äkkiä kirkkoon ja kookas
papilliseen pukuun verhottu mies astui hämärään Herran
huoneeseen. Hän oli Suomen piispa Hemming. Nopeasti oli hän
tullut, mutta astuttuaan kirkkoon hän seisahtui. Rukoilemaan ei hän
ollut tullut, vaan katseensa oli kääntynyt lähellä pääalttaria olevaan
Pyhän Laurin kuoriin. Täällä kaikki kynttilät paloivat ja viimeisiä juuri
sytytteli aivan valkotukkainen vanhus, jonka piispa tunsi kirkon
kaniikiksi Henricus Tempiliksi. Vanhus oli noussut pienelle rahille ja
kepin päähän pistetyllä pienellä kynttilällä sytytti hän alttarilla olevia
korkeita äskettäin ulkomailta tuoduissa hopeisissa kynttilänjaloissa
palavia kynttilöitä. Jo paloivat kaikki, hän laskeutui rahilta, siirsi sen
syrjään, teki syvään ristinmerkin alttarilla olevalle lippaalle, jossa oli
Pyhän Henrikin pyhäinjäännökset ja kääntyi sitten kirkkoon päin.
Tällöin näki hän äsken tulleen henkilön ja tunnettuaan hänet
piispaksi hän kumarsi tälle syvään, niin syvään, että kumarasta
nouseminen tuntui vanhukselle vaikealta.
Rypistetyin silmäkulmin astui piispa kaniikin eteen ja sanoi: —
Miksi keskellä yötä olet sytyttänyt kaikki kynttilät palamaan alttarilla?
Tavanmukaiset yökynttilät olisivat riittäneet.

— Minä odotan tänne kansaa, sanoi vanha kaniikki.
— Odotat, sanoi piispa, siis et muista, mitä olen määrännyt?
Vanhus vaikeni, katsoi vain kivipermantoon ja kädessään vielä
oleva kynttilän sytyttäjä putosi maahan.
— Jumala on meitä rangaissut hirmuisella kuolemantaudilla, joka
riistää toisen uhrin toisensa jälkeen, jatkoi piispa. Linnanherran
kanssa olemme määränneet, että kaikki lika ja roska on kaupungissa
poltettava, että suurinta puhtautta on pidettävä ja että sairaat ovat
eroitettavat terveistä. Ainoastaan näin voimme pelastaa ihmiset
hirmukuolemasta. Kirkko on määrätty suljettavaksi ja ihmisiä
käsketty kääntymään pyhien puoleen kodeissaan. Oletko kaiken
tämän unhottanut?
— En, herrani ja esimieheni, sanoi kaniikki hiljaa ja nöyrästi, mutta
minä olen säälinyt heitä ja vastoin tahtoasi luvannut avata heille
kirkon, jotta he saisivat anoa apua Pyhältä Henrikiltä. Sinä sanoit
meneväsi Koroisiin piispantaloon. Minä en tiennyt sinun olevan
täällä.
— Sinä olet rikkonut kirkon asettamat säännöt; tiedät siis, että
siitä sinua kohtaa rangaistus, sanoi piispa kiivaasti.
— Minä tiedän sen ja olen valmis ottamaan sen vastaan.
— Miksi siis tämän kaiken tahdoit tehdä?
— Johan minä sen sanoin sinulle, vastasi kaniikki lempeästi, ja
tällä kertaa uskaltaen katsoa kirkkailla harmailla silmillään piispaan,
— minä säälin heitä, noita kuolevia ja pelastustaan etsiviä. Minun
herrani ja esimieheni, elä suutu minuun siitä, ett'en ole voinut nähdä

kaikkia samoilla silmillä kuin sinä. Katsohan, ihminen voi pelastaa
ruumiinsa ja kuitenkin pysyä sairaana, ell'ei hänellä ole uskoa. Hän
voi kuolla ja kuitenkin elää iankaikkisesti, jos hänellä on usko. Sinä
olet tahtonut estää heitä pääsemästä kirkkoon, jossa heidän uskonsa
saisi uutta voimaa. Minä olen sinun halpa palvelijasi ja sinä olet
minun herrani ja piispani, jonka kirkko on esimiehekseni asettanut,
mutta kuule kuitenkin minua, joka jo olen lähellä ihmisijän suurta
rajaa ja joka ikävöitsen herrani ja jumalani luo. Paljon olet sinä tässä
maassa tehnyt, jotta herran temppeli kaunistuisi ja sen kautta
jumalan iankaikkinen kunnia loistoonsa tulisi, paljon olet saanut
kunniaa siitä, että Birgitta rouva, jonka asioissa juuri hiljattain olit
pyhän isän luona Avignonissa, sinua ystävyydellään kunnioittaa.
Olethan hänessä nähnyt, mitä suuri usko saa aikaan ja kuinka
jumala häntä on armoittanut antaessaan hänelle unessa ilmestyksiä.
Ymmärrä nyt näitä halpoja olentoja, jotka hädässään tahtovat paeta
jumalan luo ja etsivät turvaansa Herran huoneessa Pyhän Henrikin
lippaan luona.
— Taitavasti osaat, Henricus Tempil, sanasi asettaa, lausui piispa,
ja ovelasti riistät vastustuksen minun käsistäni. Mutta kuitenkin
täytyy meidän tässä asiassa toimia toisin kuin nyt ajattelet. Katso
tautia, joka maata vitsoo, seuraa, miten se leviää, niin näet, että
lopetat koko kaupungin, jos päästät ihmiset kirkkoon. Jokainen, joka
lähestyy tällaista sairasta, saa itse taudin, jokainen, joka koskettaa
esineeseen, mikä tällaisella kuolleella on ollut, näkee ruumiinsa
kohta täyttyvän paiseilla ja kuoleman leimanneen hänetkin. Asetu
kirkon portaille, vihmo heitä pyhällä vedellä, jotta kansa saisi
lohdutuksensa, mutta elä päästä heitä Herran huoneeseen, sillä
täällä he kaikki saavat kuoleman.

— Herrani ja esimieheni, sinä puhut viisaasti, mutta yhden asian
olet unohtanut. Sinun ei pidä astua yksinkertaisen uskon tielle.
Piispa katsoi pitkään vanhuksen kirkkaisiin silmiin, joissa kyyneleet
välkkyivät. Hän taputti vanhusta hiljaa olalle ja sanoi:
— Herra sinua palkitkoon suuren laupiaan sydämmesi tähden.
Hän aikoi jatkaa, kun korvansa eroittivat omituista ääntä ulkoa.
Se oli kummallista kumeaa jyskytystä, epätasaista ja kaamoittavaa
ja sen ohella kuului valittavia ääniä.
— Mitä se on? kysyi piispa.
— He saapuvat, vastasi kaniikki.
— Mikä on tuo kumea ääni, aivan kuin hiljaa jyskytettäisiin
arkkuun?
— Minä menen katsomaan.
Vanhus aikoi kiiruhtaa kirkon ovea kohden, kun piispa hänet pidätti
ja sanoi:
— Elä mene! Ovea ei avata. Sammuta alttarin kynttilät, jotta he
eivät näkisi valoa ikkunoista. Minä menen puhumaan heille oven läpi.
Nopeasti astui piispa kirkon suurta ovea kohti ja kaniikki meni
Pyhän Laurin kuoriin sammuttamaan kynttilöitä. Mutta hän ei tätä
tehnytkään, vaan jäi kuuntelemaan, mitä piispansa aikoi puhua
ulkona oleville.

— Kuka siellä? kysyi Hemming piispa ja hänen äänensä kaikui
voimakkaana kirkon holvissa.
— Me olemme tulleet rukoilemaan Pyhän Henrikin lippaan luona,
niinkuin meille lupasit, kuului ääni oven takaa.
— Mitä kaniikki on luvannut, sen piispa kieltää, sanoi Hemming.
Hetkisen oli oven takana hiljaista tämän lauseen jälkeen, sitten
kuului miehen ääni:
— Me tahdomme tulla kirkkoon, meidän täytyy sinne päästä!
Samassa kuului kumea jysähdys oveen.
— Kirkon kirous seuraa sitä, joka väkisin tunkeutuu Herran
huoneeseen! huusi piispa.
Mutta hänen äänensä hukkui kumeaan jyskeeseen. Ensin kuului
säännöllisesti palaava lyönti, aivan kuin hirrellä olisi oveen isketty,
sitten kuului toinen tämän rinnalla, kohta kolmas ja neljäs. Vahva
tammiovi tärisi ja suuri rautalukko vinkui ja saranat narskuivat. Yhä
tiheämpään osuivat iskut, voimakkaimmin sille kohtaa, missä lukko
oli. Jo erkani määrly, kohta toinen ja piispa huomasi oven pian
aukenevan. Hän kiirehti kirkon perälle pääkuoriin asti, sulkien
ristikon, joka sen eroitti muusta kirkosta. Paksun tammioven takaa
kuului jysähdysten ohella ääniä, yhä voimakkaammin ja yhä
kiihkeämmin. Äkkiä ovi ponnahti selälleen, lyödä jysähti seinään. Ja
silloin oli äkkiä kaikki jälleen hiljaista.
Kansa, joka väkivalloin oli oven murtanut, arkaili sen auettua.
Mutta ensimäisinä olleet astuivat sisään. Ja silloin piispa kalpeni
katsellessaan heitä. Monet olivat laatineet suuria ristejä puusta ja

niitä he kantoivat selässään. Näillä he olivat kirkon oven murtaneet.
Muuan kookas mies, varmaankin se, joka kiivaimmin oli iskenyt,
horjui ristiään kantaen ensimäisenä eteenpäin. Kun hän oli
muutaman askeleen astunut, pettivät hänen voimansa ja hän vaipui
ensin polvilleen ja sitten suulleen maahan, jolloin risti toisella
sivuhaarallaan jysähti kirkon kivipermantoon ja sen kumahdus kaikui
holvissa. Mutta kukaan ei häntä mennyt auttamaan. Muutamat
astuivat hänen ohitsensa, pari hänen ylitsensäkin ja joukko terveitä
ja sairaita alkoi liikkua Pyhän Laurin alttaria kohden. Pian ensimäiset
laskeutuivat polvilleen ja sitä seurasivat muutkin. Terveet matelivat
eteenpäin koko ajan hymisten rukouksia ja sairaat takertuivat heihin
ja valittaen pyysivät heiltä apua.
Vavisten katseli piispa alttarilta tätä tummaa hämärässä liikkuvaa
joukkoa, joka lainehti hiljaa eteenpäin. Siellä täällä kohosi risti muun
joukon yläpuolelle ja kuului kumeaa jysähtelyä, kun kaksi sellaista
liikahtaessaan kolahti yhteen. Mutta rauhallisena ja tyynenä seisoi
vanha Henricus kädet ristissä alttarin edessä, jolla oli Pyhän Henrikin
lipas, ja autuaallinen hymy oli hänen huulillaan. Ja kun kansa oli
tullut hänen lähelleen, ojensi hän kätensä tämän joukon yli ja siunasi
heitä.
Rautainen aita eroitti Pyhän Laurin kuorin muusta kirkosta, tämän
ristikon rautojen läpi monet käsiään ojensivat pyhää lipasta kohti. Ja
vanhus kääntyi alttarille päin, otti kauniisti kirjaillun vaatteen
käsiinsä, jotta ei paljailla käsillään koskettaisi pyhään esineeseen ja
nosti alttarilta lippaan. Ja kun hän jälleen kääntyi kansan puoleen
astui hän aivan ristikon luo, ja ojensi lippaan niin, että lähinnä olevat
saattoivat sitä suudella. Pääalttarin ristikon takaa piispa tätä katsoi ja
tietämättään mitä hän teki hänkin vaipui polvilleen ja löi otsansa
kirkon lattiaan.

Polvillaan oli kansa ristikon takana, mutta muuan nuori tyttö oli
noussut seisomaan ja piteli käsillään kiinni ristikosta, jotta ei kaatuisi,
sillä hänen silmänsä harhailivat ja jalkansa horjuivat ja hänen
kasvoillaan ja käsissään oli suuria tummia pilkkuja. Kun lipas tuli
hänen kohdalleen, kokosi hän viimeiset voimansa, suuteli sitä. Äkkiä
kädet erkaantuivat, hän kirkaisi:
— Minä olen terve, minä olen terve!
Ja tämän sanottuaan hän kaatui taapäin ja toiset ottivat hänet
vastaan ja laskivat lattialle. Ja kaikkien rinnasta pääsi iloinen
huudahdus:
— Ihme! Ihme! Pyhä on tehnyt ihmeen!
Silloin piispa nosti päänsä, kohosi seisaalleen ja katsoi kurotetuin
kauloin Pyhän Laurin kuoriin päin. Hänen ja kaniikin katseet yhtyivät
ja piispa luki vanhan Henricuksen silmistä suuren ilon.
Piispan teki mieli huutaa, että ihmiset pettivät itseään, ett'ei tässä
ollut mitään totta, että tytön huudahdus oli ollut vain viimeinen
kuolonkamppailu. Mutta oli aivan kuin jokin voima olisi tukkinut
hänen suunsa, hän ei voinut päästää ääntäkään. Hän teki
ristinmerkin alttarille päin, polvistui ja hiipi sakastin kautta pois,
ihmisten riemuhuutojen soidessa korvissaan.
Päiväksi valkeneva kesäyö verhosi kaupunkia. Piispa ei nähnyt
taivaan ihmeellistä kauneutta, ei huomannut ihmisiä, jotka hänen
ohitse kulkiessaan paljastivat päänsä ja odottivat hänen siunaustaan.
Hän asteli vain eteenpäin tietämättä minne. Kun hän oli päässyt
ulkopuolelle kaupunkia, istahti hän eräälle mäen töyrylle. Hän painoi
päänsä käsiinsä ja istui kauan mietteissään. Kun hän kasvonsa

kohotti, katseli hän luontoa. Kaikki oli kellastunutta ja kuollutta, sillä
kesä oli ollut kovin helteinen eikä vettä ollut satanut pitkään aikaan.
Aamuilmassa hän tunsi omituista löyhkää. Lähellä oli talo, hän
suuntasi sinnepäin katseensa ja näki, miten sen pihalla makasi
ruumiita, ja kun hän terästi katsettaan, huomasi hän, miten linnut
istuivat niiden kasvoilla ja nokkivat silmiä. Pellolla, jota ei kukaan
ollut leikannut, käveli karjaa ja söi tuleentunutta ruista. Hän kuuli
erään lehmän surkeasti ammuvan. Sen utareet olivat täynnä, eikä
missään ollut lypsäjää.
Silloin piispa nousi paikaltaan, astui eläimen luo ja ottaen
piispanhatun päästään alkoi siihen lypsää. Ja lehmä seisoi
liikkumatta paikallaan, silloin tällöin vain kääntäen päänsä
tuntiessaan oudon lypsäjän.
Ja kantaen lakkiaan, jossa maito hiljaa lainehteli, hän kohtasi tien
vieressä kuolevan miehen, joka anoi juotavaa. Ja piispa kumartui
hänen puoleensa, nosti kuolevan pään polvensa nojaan ja virvoitti
häntä maidolla. Eikä hän sinä hetkenä kuolemaa ja taudin vaaraa
pelännyt.
Pitkälle oli päivä jo kulunut, kun hän taas palasi tuomiokirkkoon ja
astui sakastin kautta sisään. Kirkko oli tyhjä. Permannolla vain virui
joukko ruumiita, joita muuan mies, jolla oli kasvojen edessä peite ja
käsissään nahkakintaat, kuletti kirkosta pois iskien heihin pitkän
kepin päässä olevalla koukulla ja laahaten ne sitten ovesta ulos.
Mutta pyhän Laurin kuorissa oli alttarin edessä vanha kaniikki
polvillaan rukoukseen vaipuneena. Piispa astui hiljaa kuoria kohden,
avasi ristikon ja polvistui vanhuksen viereen.

— Herra, Herra, sanoi hän kohottaen kasvonsa taivasta kohden,
olet opettanut minut ymmärtämään, kuinka vähän ihmistä hyödyttää
ruumiinsa säilyttäminen, jos hän menettää sielunsa.
Jalmari Finne.

KAKSI MADONNAA.
Piispantalon portista tuiskahti turulle pienehkö mies, vanha miehen
käkkyrä.
Olivat jo kumarasillaan ukon hartiat, mutta ketterästi hän käydä
tuiversi, niin että heiskahtelivat vain tummahkon porvariskauhtanan
liepeet ihonmukaisia housuja vasten. Tiuhaan pistättivät syyspäivän
lämmittämää tanhuaa kurpposet, joiden ruojut ylettivät nipinnapin
nilkkaan. Tiuhaan nyökähteli uurreotsainen pää, pannen tasalatvaksi
leikatun tumman tukan hepsahtelemaan, ja kun hän Kirkkoturun
kaakkoisesta kainalosta käännähti Napaturunkatua itäänpäin,
jännittyi hänen käsivartensa koukkuun ikäänkuin temmaistakseen
askelille vinhempaa vauhtia.
… Aina se piispa vanhus kutsui juuri hänet todistamaan
papereitaan, lahja- ja kauppakirjojaan! Olisi väliin saanut muitakin
kiskoa työstään, keskellä kaunista arkipäivää! Mutta ei kai pitänyt
muiden nimeä niin pätevänä… ja kukapa muuten hänen armolleen
maallikoista lie ollutkaan yhtä likeinen… hänhän kuului melkein
hengellisiin, ja asuikin niin lähellä…

Welcome to our website – the perfect destination for book lovers and
knowledge seekers. We believe that every book holds a new world,
offering opportunities for learning, discovery, and personal growth.
That’s why we are dedicated to bringing you a diverse collection of
books, ranging from classic literature and specialized publications to
self-development guides and children's books.
More than just a book-buying platform, we strive to be a bridge
connecting you with timeless cultural and intellectual values. With an
elegant, user-friendly interface and a smart search system, you can
quickly find the books that best suit your interests. Additionally,
our special promotions and home delivery services help you save time
and fully enjoy the joy of reading.
Join us on a journey of knowledge exploration, passion nurturing, and
personal growth every day!
ebookbell.com

Combinatorics Of Genome Rearrangements Guillaume Fertin

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Combinatorics Of Genome Rearrangements Guillaume Fertin

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 18

Slide 20

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 32

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Slide 80

Slide 81

Slide 82

Slide 83

Slide 84