New Upstream Snapshot - miniasm
Ready changes
Summary
Merged new upstream version: 0.3+git20191007.1.ce615d1+dfsg (was: 0.3+dfsg).
Resulting package
Built on 2023-01-20T02:03 (took 4m5s)
The resulting binary packages can be installed (if you have the apt repository enabled) by running one of:
apt install -t fresh-snapshots miniasm-dbgsymapt install -t fresh-snapshots miniasm
Diff
diff --git a/.gitignore b/.gitignore
deleted file mode 100644
index 8698ab5..0000000
--- a/.gitignore
+++ /dev/null
@@ -1,4 +0,0 @@
-.*.swp
-*.o
-*.a
-Makefile.bak
diff --git a/PAF.md b/PAF.md
index 7d0fdf9..6505edb 100644
--- a/PAF.md
+++ b/PAF.md
@@ -8,8 +8,8 @@ following predefined fields:
|--:|:----:|:-----------------------------------------|
|1 |string|Query sequence name |
|2 |int |Query sequence length |
-|3 |int |Query start (0-based) |
-|4 |int |Query end (0-based) |
+|3 |int |Query start (0-based; BED-like; closed) |
+|4 |int |Query end (0-based; BED-like; open) |
|5 |char |Relative strand: "+" or "-" |
|6 |string|Target sequence name |
|7 |int |Target sequence length |
diff --git a/README.md b/README.md
index 9a1e42b..18cda25 100644
--- a/README.md
+++ b/README.md
@@ -7,8 +7,8 @@ ln -s selfSampleData/pacbio_filtered.fastq reads.fq
# Install minimap and miniasm (requiring gcc and zlib)
git clone https://github.com/lh3/minimap2 && (cd minimap2 && make)
git clone https://github.com/lh3/miniasm && (cd miniasm && make)
-# Overlap for PacBio reads (or use "-x map-ont" for nanopore read overlapping)
-minimap2/minimap2 -x map-pb -t8 pb-reads.fq pb-reads.fq | gzip -1 > reads.paf.gz
+# Overlap for PacBio reads (or use "-x ava-ont" for nanopore read overlapping)
+minimap2/minimap2 -x ava-pb -t8 pb-reads.fq pb-reads.fq | gzip -1 > reads.paf.gz
# Layout
miniasm/miniasm -f reads.fq reads.paf.gz > reads.gfa
```
diff --git a/asm.c b/asm.c
index 05610c4..c00e339 100644
--- a/asm.c
+++ b/asm.c
@@ -82,6 +82,10 @@ void ma_ug_print(const ma_ug_t *ug, const sdict_t *d, const ma_sub_t *sub, FILE
ma_utg_t *p = &ug->u.a[i];
sprintf(name, "utg%.6d%c", i + 1, "lc"[p->circ]);
fprintf(fp, "S\t%s\t%s\tLN:i:%d\n", name, p->s? p->s : "*", p->len);
+ if (p->circ) { // make circularising links (both forward and reverse directions) for circular unitigs
+ fprintf(fp, "L\t%s\t+\t%s\t+\t0M\n", name, name);
+ fprintf(fp, "L\t%s\t-\t%s\t-\t0M\n", name, name);
+ }
for (j = l = 0; j < p->n; l += (uint32_t)p->a[j++]) {
uint32_t x = p->a[j]>>33;
if (sub) fprintf(fp, "a\t%s\t%d\t%s:%d-%d\t%c\t%d\n", name, l, d->seq[x].name, sub[x].s + 1, sub[x].e, "+-"[p->a[j]>>32&1], (uint32_t)p->a[j]);
diff --git a/debian/changelog b/debian/changelog
index 6cedf48..70a0b8e 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+miniasm (0.3+git20191007.1.ce615d1+dfsg-1) UNRELEASED; urgency=low
+
+ * New upstream snapshot.
+
+ -- Debian Janitor <janitor@jelmer.uk> Fri, 20 Jan 2023 02:00:33 -0000
+
miniasm (0.3+dfsg-4) unstable; urgency=medium
* Bump Standards-Version.
diff --git a/debian/patches/ensure_64bit_value b/debian/patches/ensure_64bit_value
index 1e59686..c04c177 100644
--- a/debian/patches/ensure_64bit_value
+++ b/debian/patches/ensure_64bit_value
@@ -5,8 +5,10 @@ Author: Sascha Steinbiss <sascha@steinbiss.name>
Forwarded: https://github.com/lh3/minimap/pull/2
Applied-Upstream: https://github.com/lh3/minimap/commit/1cd6ae3bc7c7a6f9e7c03c0b7a93a12647bba244
Last-Update: 2016-01-14
---- a/kdq.h
-+++ b/kdq.h
+Index: miniasm.git/kdq.h
+===================================================================
+--- miniasm.git.orig/kdq.h
++++ miniasm.git/kdq.h
@@ -1,12 +1,13 @@
#ifndef __AC_KDQ_H
#define __AC_KDQ_H
diff --git a/debian/patches/hardening b/debian/patches/hardening
index 73456a9..3846fd4 100644
--- a/debian/patches/hardening
+++ b/debian/patches/hardening
@@ -1,8 +1,10 @@
Description: add hardening flags
Author: Sascha Steinbiss <sascha@steinbiss.name>
Last-Update: 2016-01-14
---- a/Makefile
-+++ b/Makefile
+Index: miniasm.git/Makefile
+===================================================================
+--- miniasm.git.orig/Makefile
++++ miniasm.git/Makefile
@@ -1,6 +1,5 @@
CC= gcc
-CFLAGS= -g -Wall -O2 -Wc++-compat
diff --git a/debian/patches/spelling b/debian/patches/spelling
index e78d706..91e87bb 100644
--- a/debian/patches/spelling
+++ b/debian/patches/spelling
@@ -1,7 +1,9 @@
Description: spelling
Author: Sascha Steinbiss <satta@debian.org>
---- a/miniasm.1
-+++ b/miniasm.1
+Index: miniasm.git/miniasm.1
+===================================================================
+--- miniasm.git.orig/miniasm.1
++++ miniasm.git/miniasm.1
@@ -153,7 +153,7 @@ sequences.
Max and min overlap drop ratio [0.7,0.5]. Let overlap(v->w) be the overlap
length of edge v->w and maxovlp(v)=max_w{overlap(v->w)} be the length of
diff --git a/tex/Makefile b/tex/Makefile
new file mode 100644
index 0000000..ec4a72c
--- /dev/null
+++ b/tex/Makefile
@@ -0,0 +1,18 @@
+.SUFFIXES: .gp .tex .eps .pdf .eps.gz
+
+.eps.pdf:
+ epstopdf --outfile $@ $<
+
+.eps.gz.pdf:
+ gzip -dc $< | epstopdf --filter > $@
+
+.pdf.eps:
+ pdftops -eps $< $@
+
+all:miniasm.pdf
+
+miniasm.pdf:miniasm.tex miniasm.bib
+ pdflatex miniasm; bibtex miniasm; pdflatex miniasm; pdflatex miniasm;
+
+clean:
+ rm -fr *.toc *.aux *.bbl *.blg *.idx *.log *.out *~ miniasm.pdf
diff --git a/tex/bioinfo.cls b/tex/bioinfo.cls
new file mode 100644
index 0000000..caa6b59
--- /dev/null
+++ b/tex/bioinfo.cls
@@ -0,0 +1,927 @@
+\newcommand\classname{bioinfo}
+\newcommand\lastmodifieddate{2003/02/08}
+\newcommand\versionnumber{0.1}
+
+% Are we printing crop marks?
+\newif\if@cropmarkson \@cropmarksontrue
+
+\NeedsTeXFormat{LaTeX2e}[2001/06/01]
+\ProvidesClass{\classname}[\lastmodifieddate\space\versionnumber]
+
+\setlength{\paperheight}{11truein}
+\setlength{\paperwidth}{8.5truein}
+
+\newif\if@final
+
+\DeclareOption{draft}{\PassOptionsToPackage{draft}{graphicx}}
+\DeclareOption{a4paper}{\PassOptionsToPackage{a4}{crop}}
+\DeclareOption{centre}{\PassOptionsToPackage{center}{crop}}
+\DeclareOption{crop}{\PassOptionsToPackage{cam}{crop}\global\@cropmarksontrue}
+\DeclareOption{nocrop}{\PassOptionsToPackage{off}{crop}\global\@cropmarksonfalse}
+\DeclareOption{info}{\PassOptionsToPackage{info}{crop}}
+\DeclareOption{noinfo}{\PassOptionsToPackage{noinfo}{crop}}
+\DeclareOption{final}{\global\@finaltrue}
+
+\ExecuteOptions{a4paper,nocrop,centre,info}
+
+\ProcessOptions
+
+% Load all necessary packages
+\RequirePackage{inputenc,crop,graphicx,amsmath,array,color,amssymb,flushend,stfloats,amsthm,chngpage,times}
+%\RequirePackage[LY1]{fontenc}
+%\RequirePackage[LY1,mtbold]{mathtime}
+\def\helvetica{\fontfamily{phv}\selectfont}
+\def\helveticaitalic{\fontfamily{phv}\itshape\selectfont}
+\def\helveticabold{\fontfamily{phv}\bfseries\selectfont}
+\def\helveticabolditalic{\fontfamily{phv}\bfseries\itshape\selectfont}
+
+% Not sure if needed.
+\newcommand\@ptsize{0}
+
+% Set twoside printing
+\@twosidetrue
+
+% Marginal notes are on the outside edge
+\@mparswitchfalse
+
+\reversemarginpar
+
+\renewcommand\normalsize{%
+ \@setfontsize\normalsize{9}{11}%
+ \abovedisplayskip 10\p@ \@plus2\p@ \@minus5\p@
+ \abovedisplayshortskip \z@ \@plus3\p@
+ \belowdisplayshortskip 6\p@ \@plus3\p@ \@minus3\p@
+ \belowdisplayskip \abovedisplayskip
+ \let\@listi\@listI}
+\normalsize
+\let\@bls\baselineskip
+
+\newcommand\small{%
+ \@setfontsize\small{9}{11}%
+ \abovedisplayskip 11\p@ minus 3\p@
+ \belowdisplayskip \abovedisplayskip
+ \abovedisplayshortskip \z@ plus 2\p@
+ \belowdisplayshortskip 4\p@ plus 2\p@ minus2\p@
+ \def\@listi{\topsep 4.5\p@ plus 2\p@ minus 1\p@
+ \itemsep \parsep
+ \topsep 4\p@ plus 2\p@ minus 2\p@}}
+
+\newcommand\footnotesize{%
+ \@setfontsize\footnotesize{8}{10}%
+ \abovedisplayskip 6\p@ minus 3\p@
+ \belowdisplayskip\abovedisplayskip
+ \abovedisplayshortskip \z@ plus 3\p@
+ \belowdisplayshortskip 6\p@ plus 3\p@ minus 3\p@
+ \def\@listi{\topsep 3\p@ plus 1\p@ minus 1\p@
+ \parsep 2\p@ plus 1\p@ minus 1\p@\itemsep \parsep}}
+
+\def\scriptsize{\@setfontsize\scriptsize{7pt}{9pt}}
+\def\tiny{\@setfontsize\tiny{5pt}{7pt}}
+\def\large{\@setfontsize\large{11.5pt}{12pt}}
+\def\Large{\@setfontsize\Large{14pt}{16}}
+\def\LARGE{\@setfontsize\LARGE{15pt}{17pt}}
+\def\huge{\@setfontsize\huge{22pt}{22pt}}
+\def\Huge{\@setfontsize\Huge{30pt}{30pt}}
+
+\DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
+\DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
+\DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
+\DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
+\DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
+\DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
+\DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}
+
+% Line spacing
+\setlength\lineskip{1\p@}
+\setlength\normallineskip{1\p@}
+\renewcommand\baselinestretch{}
+
+% Paragraph dimensions and inter-para spacing
+\setlength\parskip{0\p@}
+\setlength\parindent{3mm}
+
+% Set inter-para skips
+\setlength\smallskipamount{3\p@ \@plus 1\p@ \@minus 1\p@}
+\setlength\medskipamount{6\p@ \@plus 2\p@}
+\setlength\bigskipamount{12\p@ \@plus 4\p@ \@minus 4\p@}
+
+% Page break penalties
+\@lowpenalty 51
+\@medpenalty 151
+\@highpenalty 301
+
+% Disallow widows and orphans
+\clubpenalty 10000
+\widowpenalty 10000
+
+% Disable page breaks before equations, allow pagebreaks after
+% equations and discourage widow lines before equations.
+\displaywidowpenalty 100
+\predisplaypenalty 10000
+\postdisplaypenalty 2500
+
+% Allow breaking the page in the middle of a paragraph
+\interlinepenalty 0
+
+% Disallow breaking the page after a hyphenated line
+\brokenpenalty 10000
+
+% Hyphenation; don't split words into less than three characters
+\lefthyphenmin=3
+\righthyphenmin=3
+
+%
+% Set page layout dimensions
+%
+\setlength\headheight{16\p@} % height of running head
+\setlength\topmargin{2.9pc} % head margin
+\addtolength\topmargin{-1in} % subtract out the 1 inch driver margin
+
+\setlength\topskip{10\p@} % height of first line of text
+\setlength\headsep{19\p@} % space below running head --
+
+\setlength\footskip{34\p@} % space above footer line
+\setlength\maxdepth{.5\topskip} % pages can be short or deep by half a line?
+
+\setlength\textwidth{42pc} % text measure excluding margins
+
+\setlength\textheight{58\baselineskip} % 54 lines on a full page,
+\addtolength\textheight{\topskip} % including the first
+ % line on the page
+
+% Set the margins
+\setlength\marginparsep{3\p@}
+\setlength\marginparpush{3\p@}
+\setlength\marginparwidth{35\p@}
+
+\setlength\oddsidemargin{4.5pc}
+\addtolength\oddsidemargin{-1in} % subtract out the 1 inch driver margin
+\setlength\@tempdima{\paperwidth}
+\addtolength\@tempdima{-\textwidth}
+\addtolength\@tempdima{-4.5pc}
+\setlength\evensidemargin{\@tempdima}
+\addtolength\evensidemargin{-1in}
+
+\setlength\columnsep{1.5pc} % space between columns for double-column text
+\setlength\columnseprule{0\p@} % width of rule between two columns
+
+% Footnotes
+\setlength\footnotesep{9\p@} % space between footnotes
+% space between text and footnote
+\setlength{\skip\footins}{12\p@ \@plus 6\p@ \@minus 1\p@}
+
+% Float placement parameters
+
+% The total number of floats that can be allowed on a page.
+\setcounter{totalnumber}{10}
+% The maximum number of floats at the top and bottom of a page.
+\setcounter{topnumber}{5}
+\setcounter{bottomnumber}{5}
+% The maximum part of the top or bottom of a text page that can be
+% occupied by floats. This is set so that at least four lines of text
+% fit on the page.
+\renewcommand\topfraction{.9}
+\renewcommand\bottomfraction{.9}
+% The minimum amount of a text page that must be occupied by text.
+% This should accomodate four lines of text.
+\renewcommand\textfraction{.06}
+% The minimum amount of a float page that must be occupied by floats.
+\renewcommand\floatpagefraction{.94}
+
+% The same parameters repeated for double column output
+\renewcommand\dbltopfraction{.9}
+\renewcommand\dblfloatpagefraction{.9}
+
+% Space between floats
+\setlength\floatsep {12\p@ \@plus 2\p@ \@minus 2\p@}
+% Space between floats and text
+\setlength\textfloatsep{20\p@ \@plus 2\p@ \@minus 4\p@}
+% Space above and below an inline figure
+\setlength\intextsep {18\p@ \@plus 2\p@ \@minus 2\p@}
+
+% For double column floats
+\setlength\dblfloatsep {12\p@ \@plus 2\p@ \@minus 2\p@}
+\setlength\dbltextfloatsep{20\p@ \@plus 2\p@ \@minus 4\p@}
+
+% Space left at top, bottom and inbetween floats on a float page.
+\setlength\@fptop{0\p@} % no space above float page figures
+\setlength\@fpsep{12\p@ \@plus 1fil}
+\setlength\@fpbot{0\p@}
+
+% The same for double column
+\setlength\@dblfptop{0\p@}
+\setlength\@dblfpsep{12\p@ \@plus 1fil}
+\setlength\@dblfpbot{0\p@}
+
+% Override settings in mathtime back to TeX defaults
+\DeclareMathSizes{5} {5} {5} {5}
+\DeclareMathSizes{6} {6} {5} {5}
+\DeclareMathSizes{7} {7} {5} {5}
+\DeclareMathSizes{8} {8} {6} {5}
+\DeclareMathSizes{9} {9} {6.5} {5}
+\DeclareMathSizes{10} {10} {7.5} {5}
+\DeclareMathSizes{12} {12} {9} {7}
+
+% Page styles
+\def\ps@headings
+ {%
+ \def\@oddfoot{\vbox to 12.5\p@{\hbox{\rule{\textwidth}{0.5\p@}}\vss
+ \hbox to \textwidth{\hfill\helveticabold\small\thepage}%
+ }}%
+ \def\@evenfoot{\vbox to 12.5\p@{\rule{\textwidth}{0.5\p@}\vss
+ \hbox to \textwidth{\helveticabold\small\thepage\hfill}%
+ }}%
+ \def\@evenhead{\vbox{\hbox to \textwidth{\fontsize{8}{10}\selectfont
+ \helveticabold{\fontshape{it}\selectfont
+ \strut\leftmark}\hfill}\vspace{6.5\p@}\rule{\textwidth}{0.5\p@}}}%
+ \def\@oddhead{\vbox{\hbox to \textwidth{\hfill\fontsize{8}{10}\selectfont
+ \helveticabold{\fontshape{it}\selectfont\strut\rightmark}}%
+ \vspace{6.5\p@}\rule{\textwidth}{0.5\p@}}}%
+ \def\titlemark##1{\markboth{##1}{##1}}%
+ \def\authormark##1{\gdef\leftmark{##1}}%
+ }
+
+\def\ps@opening
+ {%
+ \def\@oddfoot{\vbox to 13\p@{\hbox{\rule{\textwidth}{1\p@}}\vss
+ \hbox to \textwidth{\helvetica
+ \fontsize{7}{9}\fontshape{n}\selectfont%
+ \hfill\small\helveticabold\thepage}%
+ }}%
+ \def\@evenfoot{\vbox to 13\p@{\rule{\textwidth}\vss
+ \hbox to \textwidth{\helvetica\thepage\hfill
+ \fontsize{7}{9}\fontshape{n}\selectfont}%
+ }}%
+ \let\@evenhead\relax
+ \let\@oddhead\relax}
+
+% Page range
+\newif\iflastpagegiven \lastpagegivenfalse
+\newcommand\firstpage[1]{%
+ \gdef\@firstpage{#1}%
+ \ifnum\@firstpage>\c@page
+ \setcounter{page}{#1}%
+ \ClassWarning{BIO}{Increasing pagenumber to \@firstpage}%
+ \else \ifnum\@firstpage<\c@page
+ \ClassWarning{BIO}{Firstpage lower than pagenumber}\fi\fi
+ \xdef\@firstpage{\the\c@page}%
+ }
+\def\@firstpage{1}
+\def\pagenumbering#1{%
+ \global\c@page \@ne
+ \gdef\thepage{\csname @#1\endcsname \c@page}%
+ \gdef\thefirstpage{%
+ \csname @#1\endcsname \@firstpage}%
+ \gdef\thelastpage{%
+ \csname @#1\endcsname \@lastpage}%
+ }
+
+\newcommand\lastpage[1]{\xdef\@lastpage{#1}%
+ \global\lastpagegiventrue}
+\def\@lastpage{0}
+\def\setlastpage{\iflastpagegiven\else
+ \edef\@tempa{@lastpage@}%
+ \expandafter
+ \ifx \csname \@tempa \endcsname \relax
+ \gdef\@lastpage{0}%
+ \else
+ \xdef\@lastpage{\@nameuse{@lastpage@}}%
+ \fi
+ \fi }
+\def\writelastpage{%
+ \iflastpagegiven \else
+ \immediate\write\@auxout%
+ {\string\global\string\@namedef{@lastpage@}{\the\c@page}}%
+ \fi
+ }
+\def\thepagerange{%
+ \ifnum\@lastpage =0 {\ \bf ???} \else
+ \ifnum\@lastpage = \@firstpage \ \thefirstpage\else
+ \thefirstpage--\thelastpage \fi\fi}
+
+\AtBeginDocument{\setlastpage
+ \pagenumbering{arabic}%
+ }
+\AtEndDocument{%
+ \writelastpage
+ \if@final
+ \clearemptydoublepage
+ \else
+ \clearpage
+ \fi}
+
+%
+% Sectional units
+%
+
+% Counters
+\newcounter{section}
+\newcounter{subsection}[section]
+\newcounter{subsubsection}[subsection]
+\newcounter{paragraph}[subsubsection]
+\newcounter{subparagraph}[paragraph]
+\newcounter{figure}
+\newcounter{table}
+
+% Form of the numbers
+\newcommand\thepage{\arabic{page}}
+\renewcommand\thesection{\arabic{section}}
+\renewcommand\thesubsection{{\thesection.\arabic{subsection}}}
+\renewcommand\thesubsubsection{{\thesubsection.\arabic{subsubsection}}}
+\renewcommand\theparagraph{\thesubsubsection.\arabic{paragraph}}
+\renewcommand\thesubparagraph{\theparagraph.\arabic{subparagraph}}
+\renewcommand\theequation{\arabic{equation}}
+
+% Form of the words
+\newcommand\contentsname{Contents}
+\newcommand\listfigurename{List of Figures}
+\newcommand\listtablename{List of Tables}
+\newcommand\partname{Part}
+\newcommand\appendixname{Appendix}
+\newcommand\abstractname{Abstract}
+\newcommand\refname{References}
+\newcommand\bibname{References}
+\newcommand\indexname{Index}
+\newcommand\figurename{Fig.}
+\newcommand\tablename{Table}
+
+% Clearemptydoublepage should really clear the running heads too
+\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}
+
+% Frontmatter, mainmatter and backmatter
+
+\newif\if@mainmatter \@mainmattertrue
+
+\newcommand\frontmatter{%
+ \clearpage
+ \@mainmatterfalse
+ \pagenumbering{roman}}
+
+\newcommand\mainmatter{%
+ \clearpage
+ \@mainmattertrue
+ \pagenumbering{arabic}}
+
+\newcommand\backmatter{%
+ \clearpage
+ \@mainmatterfalse}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TITLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\newlength{\dropfromtop}
+\setlength{\dropfromtop}{\z@}
+
+% Application Notes
+\newif\if@appnotes
+\newcommand{\application}{%
+% \setlength{\dropfromtop}{-2.25pc}%
+ \global\@appnotestrue}
+
+\long\def\title{\@ifnextchar[{\short@title}{\@@title}}
+\def\short@title[#1]{\titlemark{#1}\@@@title}
+\def\@@title#1{\authormark{#1}\@@@title{#1}}
+\long\def\@@@title#1{\gdef\@title{#1}}
+
+\long\def\author{\@ifnextchar[{\short@uthor}{\@uthor}}
+\def\short@uthor[#1]{\authormark{#1}\@@author}
+\def\@uthor#1{\authormark{#1}\@@author{#1}}
+\long\def\@@author#1{\gdef\@author{#1}}
+
+\def\vol#1{\global\def\@vol{#1}}
+\def\issue#1{\global\def\@issue{#1}}
+\def\address#1{\global\def\@issue{#1}}
+\def\history#1{\global\def\@history{#1}}
+\def\editor#1{\global\def\@editor{#1}}
+\def\pubyear#1{\global\def\@pubyear{#1}}
+\def\copyrightyear#1{\global\def\@copyrightyear{#1}}
+\def\address#1{\global\def\@address{#1}}
+\def\DOI#1{\global\def\@DOI{#1}}
+
+\definecolor{gray}{cmyk}{0, 0, 0, 0.15}
+\newlength{\extraspace}
+\setlength{\extraspace}{\z@}
+
+\newcommand\maketitle{\par
+ \begingroup
+ \renewcommand\thefootnote{\@fnsymbol\c@footnote}%
+ \def\@makefnmark{\rlap{\@textsuperscript{\normalfont\@thefnmark}}}%
+ \long\def\@makefntext##1{\parindent 3mm\noindent
+% \@textsuperscript{\normalfont\@thefnmark}\raggedright##1}%
+ \@textsuperscript{\normalfont\@thefnmark}##1}%
+ \if@twocolumn
+ \ifnum \col@number=\@ne
+ \@maketitle
+ \else
+ \twocolumn[\@maketitle]%
+ \fi
+ \else
+ \newpage
+ \global\@topnum\z@ % Prevents figures from going at top of page.
+ \@maketitle
+ \fi
+ \thispagestyle{opening}\@thanks
+ \endgroup
+ \setcounter{footnote}{0}%
+ \global\let\thanks\relax
+ \global\let\maketitle\relax
+ \global\let\@maketitle\relax
+ \global\let\@address\@empty
+ \global\let\@history\@empty
+ \global\let\@editor\@empty
+ \global\let\@thanks\@empty
+ \global\let\@author\@empty
+ \global\let\@date\@empty
+ \global\let\@title\@empty
+ \global\let\@pubyear\@empty
+ \global\let\address\relax
+ \global\let\history\relax
+ \global\let\editor\relax
+ \global\let\title\relax
+ \global\let\author\relax
+ \global\let\date\relax
+ \global\let\pubyear\relax
+ \global\let\@copyrightline\@empty
+ \global\let\and\relax
+ \@afterindentfalse\@afterheading
+}
+
+\newlength{\aboveskipchk}%for checking oddpage or evenpage top skip
+\setlength{\aboveskipchk}{\z@}%
+
+\def\@maketitle{%
+ \let\footnote\thanks
+ \clearemptydoublepage
+ \checkoddpage\ifcpoddpage\setlength{\aboveskipchk}{-3pc}\else\setlength{\aboveskipchk}{-5pc}\fi%for checking oddpage or evenpage top skip%%
+ \vspace*{\aboveskipchk}%
+ \vspace{\dropfromtop}%
+ \hbox to \textwidth{%
+ {\helvetica\itshape\bfseries\fontsize{19}{12}\selectfont {\color{gray}MANUSCRIPT}
+ \hfil
+ \if@appnotes APPLICATIONS NOTE\hfil\fi
+ }%
+\enskip \parbox[b]{11.3pc}{%
+ \helvetica
+ \flushright\fontsize{8}{10}\fontshape{it}\selectfont
+ \hfill
+ }}
+ \rule{\textwidth}{1\p@}\par%
+ \helvetica
+ \hbox to \textwidth{%
+ \parbox[t]{36.5pc}{%
+ \vspace*{1sp}
+ {\helveticabold\fontsize{16}{21}\selectfont\raggedright \@title \par}%
+ \vspace{4.5\p@}
+ {\helvetica\fontsize{13}{15}\selectfont\raggedright \@author \par}%
+ \vspace{4\p@}
+ {\helvetica\fontsize{10}{12}\selectfont\raggedright \@address \par}%
+ \vspace{4\p@}
+ %{\helvetica\fontsize{8}{10}\selectfont\raggedright \@history \par}
+ %\vspace{24\p@}
+ %{\helvetica\fontsize{10}{12}\selectfont\raggedright \@editor \par}
+ %\vspace{20\p@}
+ }%
+ }
+ \vspace{14.5\p@}%
+ \rule{\textwidth}{1\p@}%
+ \vspace{12\p@ plus 6\p@ minus 6\p@}%
+ \vspace{\extraspace}
+ }
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%% Abstract %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\newcommand{\absection}[1]{%
+ \par\noindent{\bfseries #1}\space\ignorespaces}
+
+\newenvironment{abstract}{%
+ \begingroup
+ \let\section\absection
+ \fontfamily{\sfdefault}\fontsize{8}{11}\sffamily\selectfont
+ {\fontseries{b}\selectfont ABSTRACT}\par}
+{\endgroup\bigskip\@afterheading\@afterindentfalse\vskip 12pt plus 3pt minus 1pt}
+
+% Section macros
+
+% Lowest level heading that takes a number by default
+\setcounter{secnumdepth}{3}
+
+\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname\quad}
+
+\def\section{%
+ \@startsection{section}{1}{\z@}
+ {-22\p@ plus -3\p@}{3\p@}
+ {\reset@font\raggedright\helveticabold\fontsize{10}{12}\selectfont\MakeUppercase}}
+
+\def\subsection{%
+ \@startsection{subsection}{2}{\z@}
+ {-11\p@ plus -2\p@}{3\p@}
+ {\reset@font\raggedright\mathversion{bold}\fontseries{b}\fontsize{10}{12}\selectfont}}
+
+\def\subsubsection{%
+ \@startsection{subsubsection}{3}{\z@}
+ {-11\p@ plus -1\p@}{-1em}
+ {\reset@font\normalfont\normalsize\itshape}}
+
+\def\textcolon{\text{\rm :}}
+
+ \def\paragraph{%
+ \@startsection{paragraph}{4}{\z@}
+ {-6\p@}
+ {-.4em}
+ {\reset@font\itshape}}
+
+% ********************
+% Figures and tables *
+% ********************
+
+% Table and array parameters
+\setlength\arraycolsep{.5em}
+\setlength\tabcolsep{.5em}
+\setlength\arrayrulewidth{.5pt}
+\setlength\doublerulesep{2.5pt}
+\setlength\extrarowheight{\z@}
+\renewcommand\arraystretch{1}
+
+\newlength{\abovecaptionskip}
+\newlength{\belowcaptionskip}
+\setlength{\abovecaptionskip}{13pt}
+\setlength{\belowcaptionskip}{10.5pt}
+
+\long\def\@makecaption#1#2{\vspace{\abovecaptionskip}%
+ \begingroup
+ \footnotesize
+ \textbf{#1.}\enskip{#2}\par
+ \endgroup}
+
+\long\def\@tablecaption#1#2{%
+ \begingroup
+ \footnotesize
+ \textbf{#1.}\enskip{#2\strut\par}
+ \endgroup\vspace{\belowcaptionskip}}
+
+% Table rules
+\def\toprule{\noalign{\ifnum0=`}\fi\hrule \@height 0.5pt \hrule \@height 6pt \@width 0pt \futurelet
+ \@tempa\@xhline}
+\def\midrule{\noalign{\ifnum0=`}\fi \hrule \@height 6.75pt \@width 0pt \hrule \@height 0.5pt
+ \hrule \@height 6pt \@width 0pt \futurelet \@tempa\@xhline}
+\def\botrule{\noalign{\ifnum0=`}\fi \hrule \@height 5.75pt \@width 0pt \hrule \@height 0.5pt \futurelet
+ \@tempa\@xhline}
+\def\hrulefill{\leavevmode\leaders\hrule height .5pt\hfill\kern\z@}
+
+\def\thefigure{\@arabic\c@figure}
+\def\fps@figure{tbp}
+\def\ftype@figure{1}
+\def\ext@figure{lof}
+\def\fnum@figure{\figurename~\thefigure}
+\def\figure{\@float{figure}}
+\let\endfigure\end@float
+\@namedef{figure*}{\@dblfloat{figure}}
+\@namedef{endfigure*}{\end@dblfloat}
+\def\thetable{\@arabic\c@table}
+\def\fps@table{tbp}
+\def\ftype@table{2}
+\def\ext@table{lot}
+\def\fnum@table{Table~\thetable}
+\def\table{\let\@makecaption\@tablecaption\let\source\tablesource\@float{table}}
+\def\endtable{\end@float}
+\@namedef{table*}{\let\@makecaption\@tablecaption\@dblfloat{table}}
+\@namedef{endtable*}{\end@dblfloat}
+
+\newif\if@rotate \@rotatefalse
+\newif\if@rotatecenter \@rotatecenterfalse
+\def\rotatecenter{\global\@rotatecentertrue}
+\def\rotateendcenter{\global\@rotatecenterfalse}
+\def\rotate{\global\@rotatetrue}
+\def\endrotate{\global\@rotatefalse}
+\newdimen\rotdimen
+\def\rotstart#1{\special{ps: gsave currentpoint currentpoint translate
+ #1 neg exch neg exch translate}}
+\def\rotfinish{\special{ps: currentpoint grestore moveto}}
+\def\rotl#1{\rotdimen=\ht#1\advance\rotdimen by \dp#1
+ \hbox to \rotdimen{\vbox to\wd#1{\vskip \wd#1
+ \rotstart{270 rotate}\box #1\vss}\hss}\rotfinish}
+\def\rotr#1{\rotdimen=\ht #1\advance\rotdimen by \dp#1
+ \hbox to \rotdimen{\vbox to \wd#1{\vskip \wd#1
+ \rotstart{90 rotate}\box #1\vss}\hss}\rotfinish}
+
+\newdimen\tempdime
+\newbox\temptbox
+
+% From ifmtarg.sty
+% Copyright Peter Wilson and Donald Arseneau, 2000
+\begingroup
+\catcode`\Q=3
+\long\gdef\@ifmtarg#1{\@xifmtarg#1QQ\@secondoftwo\@firstoftwo\@nil}
+\long\gdef\@xifmtarg#1#2Q#3#4#5\@nil{#4}
+\long\gdef\@ifnotmtarg#1{\@xifmtarg#1QQ\@firstofone\@gobble\@nil}
+\endgroup
+
+\def\tablesize{\@setfontsize\tablesize{8\p@}{10\p@}}
+
+\newenvironment{processtable}[3]{\setbox\temptbox=\hbox{{\tablesize #2}}%
+\tempdime\wd\temptbox\@processtable{#1}{#2}{#3}{\tempdime}}
+{\relax}
+
+\newcommand{\@processtable}[4]{%
+\if@rotate
+\setbox4=\vbox to \hsize{\vss\hbox to \textheight{%
+\begin{minipage}{#4}%
+\@ifmtarg{#1}{}{\caption{#1}}{\tablesize #2}%
+\vskip7\p@\noindent
+\parbox{#4}{\fontsize{7}{9}\selectfont #3\par}%
+\end{minipage}}\vss}%
+\rotr{4}
+\else
+\hbox to \hsize{\hss\begin{minipage}[t]{#4}%
+\vskip2.9pt
+\@ifmtarg{#1}{}{\caption{#1}}{\tablesize #2}%
+\vskip6\p@\noindent
+\parbox{#4}{\fontsize{7}{9}\selectfont #3\par}%
+\end{minipage}\hss}\fi}%
+
+\newcolumntype{P}[1]{>{\raggedright\let\\\@arraycr\hangindent1em}p{#1}}
+
+% ******************************
+% List numbering and lettering *
+% ******************************
+\def\labelenumi{{\rm\arabic{enumi}.}}
+\def\theenumi{\arabic{enumi}}
+\def\labelenumii{{\rm\alph{enumii}.}}
+\def\theenumii{\alph{enumii}}
+\def\p@enumii{\theenumi}
+\def\labelenumiii{{\rm(\arabic{enumiii})}}
+\def\theenumiii{\roman{enumiii}}
+\def\p@enumiii{\theenumi(\theenumii)}
+\def\labelenumiv{{\rm(\arabic{enumiv})}}
+\def\theenumiv{\Alph{enumiv}}
+\def\p@enumiv{\p@enumiii\theenumiii}
+\def\labelitemi{{\small$\bullet$}}
+\def\labelitemii{{\small$\bullet$}}
+\def\labelitemiii{{\small$\bullet$}}
+\def\labelitemiv{{\small$\bullet$}}
+
+\def\@listI{\leftmargin\leftmargini \topsep\medskipamount}
+\let\@listi\@listI
+\@listi
+\def\@listii{\topsep\z@\leftmargin\leftmarginii}
+\def\@listiii{\leftmargin\leftmarginiii \topsep\z@}
+\def\@listiv{\leftmargin\leftmarginiv \topsep\z@}
+\def\@listv{\leftmargin\leftmarginv \topsep\z@}
+\def\@listvi{\leftmargin\leftmarginvi \topsep\z@}
+
+\setlength{\leftmargini}{3mm}
+\setlength{\leftmarginii}{\z@}
+\setlength{\leftmarginiii}{\z@}
+\setlength{\leftmarginiv}{\z@}
+
+% Changes to the list parameters for enumerate
+\def\enumargs{%
+ \partopsep \z@
+ \itemsep 3\p@
+ \parsep \z@
+ \labelsep 0.5em
+ \listparindent \parindent
+ \itemindent \z@
+ \topsep 11\p@
+}
+
+\def\enumerate{%
+ \@ifnextchar[{\@numerate}{\@numerate[0]}}
+
+\def\@numerate[#1]{%
+ \ifnum \@enumdepth >3 \@toodeep\else
+ \advance\@enumdepth \@ne
+ \edef\@enumctr{enum\romannumeral\the\@enumdepth}
+ \list{\csname label\@enumctr\endcsname}{%
+ \enumargs
+ \setlength{\leftmargin}{\csname leftmargin\romannumeral\the\@enumdepth\endcsname}
+ \usecounter{\@enumctr}
+ \settowidth\labelwidth{#1}
+ \addtolength{\leftmargin}{\labelwidth}
+ \addtolength{\leftmargin}{\labelsep}
+ \def\makelabel##1{\hss \llap{##1}}}%
+ \fi
+ }
+\let\endenumerate\endlist
+
+% Changes to the list parameters for itemize
+\def\itemargs{%
+ \partopsep \z@
+ \itemsep 3\p@
+ \parsep \z@
+ \labelsep 0.5em
+ \rightmargin \z@
+ \listparindent \parindent
+ \itemindent \z@
+ \topsep11\p@
+}
+
+\def\itemize{%
+ \@ifnextchar[{\@itemize}{\@itemize[$\bullet$]}}
+
+\def\@itemize[#1]{%
+ \ifnum \@itemdepth >3 \@toodeep\else
+ \advance\@itemdepth \@ne
+ \edef\@itemctr{item\romannumeral\the\@itemdepth}
+ \list{\csname label\@itemctr\endcsname}{%
+ \itemargs
+ \setlength{\leftmargin}{\csname leftmargin\romannumeral\the\@itemdepth\endcsname}
+ \settowidth\labelwidth{#1}
+ \addtolength{\leftmargin}{\labelwidth}
+ \addtolength{\leftmargin}{\labelsep}
+ \def\makelabel##1{\hss \llap{##1}}}%
+ \fi
+ }
+\let\enditemize\endlist
+
+\newenvironment{unlist}{%
+ \begin{list}{}%
+ {\setlength{\labelwidth}{\z@}%
+ \setlength{\labelsep}{\z@}%
+ \setlength{\topsep}{\medskipamount}%
+ \setlength{\itemsep}{3\p@}%
+ \setlength{\leftmargin}{2em}%
+ \setlength{\itemindent}{-2em}}}
+{\end{list}}
+
+
+% ***********************
+% Quotes and Quotations *
+% ***********************
+\def\quotation{\par\begin{list}{}{
+ \setlength{\topsep}{\medskipamount}
+ \setlength{\leftmargin}{2em}%
+ \setlength{\rightmargin}{\z@}%
+ \setlength\labelwidth{0pt}%
+ \setlength\labelsep{0pt}%
+ \listparindent\parindent}%
+ \item[]}
+\def\endquotation{\end{list}}
+\let\quote\quotation
+\let\endquote\endquotation
+
+\skip\@mpfootins = \skip\footins
+\fboxsep=6\p@
+\fboxrule=1\p@
+
+% *******************
+% Table of contents *
+% *******************
+\newcommand\@pnumwidth{4em}
+\newcommand\@tocrmarg{2.55em plus 1fil}
+\newcommand\@dotsep{1000}
+\setcounter{tocdepth}{4}
+
+\def\numberline#1{\hbox to \@tempdima{{#1}}}
+
+\def\@authortocline#1#2#3#4#5{%
+ \vskip 1.5\p@
+ \ifnum #1>\c@tocdepth \else
+ {\leftskip #2\relax \rightskip \@tocrmarg \parfillskip -\rightskip
+ \parindent #2\relax\@afterindenttrue
+ \interlinepenalty\@M
+ \leavevmode
+ \@tempdima #3\relax
+ \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip
+ {\itshape #4}\nobreak
+ \leaders\hbox{$\m@th
+ \mkern \@dotsep mu\hbox{.}\mkern \@dotsep
+ mu$}\hfill
+ \nobreak
+ \hb@xt@\@pnumwidth{\hfil}%
+ \par}%
+ \fi}
+
+\newcommand*\l@author{\@authortocline{2}{0pt}{30pt}}
+\newcommand*\l@section{\@dottedtocline{3}{11pt}{20pt}}
+\newcommand*\l@subsection{\@dottedtocline{4}{31pt}{29pt}}
+\newcommand*\l@subsubsection[2]{}
+
+
+
+% ***********
+% Footnotes *
+% ***********
+
+\def\footnoterule{\noindent\rule{\columnwidth}{0.5pt}}
+\def\@makefnmark{\@textsuperscript{\normalfont\@thefnmark}}%
+\newcommand\@makefntext[1]{\noindent{\@makefnmark}\enskip#1}
+
+% ***********
+% References *
+% ***********
+
+\providecommand{\newblock}{}
+\newenvironment{thebibliography}{%
+ \section{\bibname}%
+ \begingroup
+ \small
+ \begin{list}{}{%
+ \setlength{\topsep}{\z@}%
+ \setlength{\labelsep}{\z@}%
+ \settowidth{\labelwidth}{\z@}%
+ \setlength{\leftmargin}{4mm}%
+ \setlength{\itemindent}{-4mm}}\small}
+{\end{list}\endgroup}
+
+\RequirePackage{natbib}
+
+% **********
+% Appendix *
+% **********
+\newif\ifappend % Are we in the Appendix?
+\def\appendix{\par
+ \setcounter{section}{0}
+ \setcounter{subsection}{0}
+ \appendtrue
+}
+
+%Math parameters
+
+\setlength{\jot}{5\p@}
+\mathchardef\@m=1500 % adapted value
+
+\def\frenchspacing{\sfcode`\.\@m \sfcode`\?\@m \sfcode`\!\@m
+ \sfcode`\:\@m \sfcode`\;\@m \sfcode`\,\@m}
+
+% Theorems
+\def\th@plain{%
+%% \let\thm@indent\noindent % no indent
+\thm@headfont{\quad\scshape}% heading font is bold
+\thm@notefont{\upshape\mdseries}% same as heading font
+\thm@headpunct{.}% no period after heading
+\thm@headsep 5\p@ plus\p@ minus\p@\relax
+%% \let\thm@swap\@gobble
+%% \thm@preskip\topsep
+%% \thm@postskip\theorempreskipamount
+\itshape % body font
+}
+
+\vbadness=9999
+\tolerance=9999
+\doublehyphendemerits=10000
+\doublehyphendemerits 640000 % corresponds to badness 800
+\finalhyphendemerits 1000000 % corresponds to badness 1000
+
+\flushbottom
+\frenchspacing
+\ps@headings
+\twocolumn
+
+% Screen PDF compatability
+\newcommand{\medline}[1]{%
+ \unskip\unskip\ignorespaces}
+
+
+%%%%for smaller size text
+\newenvironment{methods}{%
+ \begingroup
+\def\section{%
+ \@startsection{section}{1}{\z@}
+ {-24\p@ plus -3\p@}{4\p@}
+ {\reset@font\raggedright\helveticabold\fontsize{10}{12}\selectfont\MakeUppercase}}
+ \def\subsection{%
+ \@startsection{subsection}{2}{\z@}
+ {-5\p@ plus -2\p@}{4\p@}
+ {\reset@font\raggedright\mathversion{bold}\fontseries{b}\fontsize{10}{12}\selectfont}}
+ \def\subsubsection{%
+ \@startsection{subsubsection}{3}{\z@}
+ {-6\p@ plus -1\p@}{-1em}
+ {\reset@font\normalfont\normalsize\itshape}}
+\footnotesize
+ \par}
+{\par\endgroup\bigskip\@afterheading\@afterindentfalse}
+
+
+
+\graphicspath{{g:/artwork/oup/bioinfo/}}
+
+\language=2
+
+\hyphenation{Figure Table Figures Tables}
+
+\newcommand{\href}[2]{#2}
+
+\renewenvironment{proof}[1][\proofname]{\par
+ \normalfont \topsep6\p@\@plus6\p@\relax
+ \labelsep 0.5em
+ \trivlist
+ \item[\hskip\labelsep\hskip1em\textsc{#1}.]\ignorespaces
+}{\endtrivlist\@endpefalse}
+
+%%Different Bonds
+
+\def\sbond{\ensuremath{\raise.25ex\hbox{${-}\!\!\!\!{-}$}}\kern -.9pt}
+\def\dbond{\ensuremath{\raise.25ex\hbox{=$\!$=}}}
+\def\tbond{\ensuremath{\raise.20ex\hbox{${\equiv}\!\!\!{\equiv}$}}}
+
+% Author queries
+%\fboxsep=4\p@
+%\fboxrule=0.5\p@
+\newcommand{\query}[2][0pt]{}%
+% \marginpar{\vspace*{#1}%
+% {\parbox{\marginparwidth}{%
+% \raggedright\fontsize{6}{8}\selectfont
+% #2}}}}
+
+\renewcommand{\dag}{{\mathversion{normal}$^{\dagger}$}}
+
+\endinput
diff --git a/tex/ce.pdf b/tex/ce.pdf
new file mode 100644
index 0000000..6ac7074
Binary files /dev/null and b/tex/ce.pdf differ
diff --git a/tex/diagrams.graffle b/tex/diagrams.graffle
new file mode 100644
index 0000000..1259dcb
--- /dev/null
+++ b/tex/diagrams.graffle
@@ -0,0 +1,908 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
+<plist version="1.0">
+<dict>
+ <key>ActiveLayerIndex</key>
+ <integer>0</integer>
+ <key>ApplicationVersion</key>
+ <array>
+ <string>com.omnigroup.OmniGraffle</string>
+ <string>139.18.0.187838</string>
+ </array>
+ <key>AutoAdjust</key>
+ <true/>
+ <key>BackgroundGraphic</key>
+ <dict>
+ <key>Bounds</key>
+ <string>{{0, 0}, {576, 733}}</string>
+ <key>Class</key>
+ <string>SolidGraphic</string>
+ <key>ID</key>
+ <integer>2</integer>
+ <key>Style</key>
+ <dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ </dict>
+ <key>BaseZoom</key>
+ <integer>0</integer>
+ <key>CanvasOrigin</key>
+ <string>{0, 0}</string>
+ <key>ColumnAlign</key>
+ <integer>1</integer>
+ <key>ColumnSpacing</key>
+ <real>36</real>
+ <key>CreationDate</key>
+ <string>2015-11-16 14:46:34 +0000</string>
+ <key>Creator</key>
+ <string>Heng Li</string>
+ <key>DisplayScale</key>
+ <string>1 0/72 in = 1.0000 in</string>
+ <key>GraphDocumentVersion</key>
+ <integer>8</integer>
+ <key>GraphicsList</key>
+ <array>
+ <dict>
+ <key>Bounds</key>
+ <string>{{161, 173.5}, {9, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>ID</key>
+ <integer>23</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\fs24 \cf0 w}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{100, 137.5}, {6, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>ID</key>
+ <integer>22</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\fs24 \cf0 v}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{464, 185}, {18, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>21</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 l
+\i0 [2]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{399, 125}, {18, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>20</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 l
+\i0 [1]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{331, 185}, {22, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>19</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 e
+\i0 [2]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{209, 185}, {22, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>18</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 b
+\i0 [2]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{330.99999359250069, 124.99999651312828}, {22, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>17</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 e
+\i0 [1]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{209, 125}, {22, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>FontInfo</key>
+ <dict>
+ <key>Font</key>
+ <string>Helvetica</string>
+ <key>Size</key>
+ <real>12</real>
+ </dict>
+ <key>ID</key>
+ <integer>16</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\i\b\fs24 \cf0 b
+\i0 [1]}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Class</key>
+ <string>LineGraphic</string>
+ <key>ID</key>
+ <integer>15</integer>
+ <key>Points</key>
+ <array>
+ <string>{317, 117}</string>
+ <string>{378, 162}</string>
+ </array>
+ <key>Style</key>
+ <dict>
+ <key>stroke</key>
+ <dict>
+ <key>HeadArrow</key>
+ <string>FilledArrow</string>
+ <key>Legacy</key>
+ <true/>
+ <key>LineType</key>
+ <integer>1</integer>
+ <key>Pattern</key>
+ <integer>1</integer>
+ <key>TailArrow</key>
+ <string>0</string>
+ </dict>
+ </dict>
+ </dict>
+ <dict>
+ <key>Class</key>
+ <string>LineGraphic</string>
+ <key>ID</key>
+ <integer>13</integer>
+ <key>Points</key>
+ <array>
+ <string>{223, 117}</string>
+ <string>{189, 162}</string>
+ </array>
+ <key>Style</key>
+ <dict>
+ <key>stroke</key>
+ <dict>
+ <key>HeadArrow</key>
+ <string>FilledArrow</string>
+ <key>Legacy</key>
+ <true/>
+ <key>LineType</key>
+ <integer>1</integer>
+ <key>Pattern</key>
+ <integer>1</integer>
+ <key>TailArrow</key>
+ <string>0</string>
+ </dict>
+ </dict>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{225, 104}, {90, 14}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>FitText</key>
+ <string>YES</string>
+ <key>Flow</key>
+ <string>Resize</string>
+ <key>ID</key>
+ <integer>11</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Pad</key>
+ <integer>0</integer>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Overhang region}</string>
+ <key>VerticalPad</key>
+ <integer>0</integer>
+ </dict>
+ <key>Wrap</key>
+ <string>NO</string>
+ </dict>
+ <dict>
+ <key>Class</key>
+ <string>LineGraphic</string>
+ <key>ID</key>
+ <integer>6</integer>
+ <key>Points</key>
+ <array>
+ <string>{180, 180}</string>
+ <string>{468, 180}</string>
+ </array>
+ <key>Style</key>
+ <dict>
+ <key>stroke</key>
+ <dict>
+ <key>HeadArrow</key>
+ <string>0</string>
+ <key>Legacy</key>
+ <true/>
+ <key>LineType</key>
+ <integer>1</integer>
+ <key>TailArrow</key>
+ <string>0</string>
+ <key>Width</key>
+ <real>3</real>
+ </dict>
+ </dict>
+ </dict>
+ <dict>
+ <key>Class</key>
+ <string>LineGraphic</string>
+ <key>ID</key>
+ <integer>5</integer>
+ <key>Points</key>
+ <array>
+ <string>{117, 144}</string>
+ <string>{405, 144}</string>
+ </array>
+ <key>Style</key>
+ <dict>
+ <key>stroke</key>
+ <dict>
+ <key>HeadArrow</key>
+ <string>0</string>
+ <key>Legacy</key>
+ <true/>
+ <key>LineType</key>
+ <integer>1</integer>
+ <key>TailArrow</key>
+ <string>0</string>
+ <key>Width</key>
+ <real>3</real>
+ </dict>
+ </dict>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{216, 144}, {126, 36}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>ID</key>
+ <integer>4</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Color</key>
+ <dict>
+ <key>b</key>
+ <string>0.6</string>
+ <key>g</key>
+ <string>0.6</string>
+ <key>r</key>
+ <string>0.6</string>
+ </dict>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ </dict>
+ <key>Text</key>
+ <dict>
+ <key>Text</key>
+ <string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 mapped region}</string>
+ </dict>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{342, 144}, {63, 36}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>ID</key>
+ <integer>10</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Color</key>
+ <dict>
+ <key>b</key>
+ <string>0.901961</string>
+ <key>g</key>
+ <string>0.901961</string>
+ <key>r</key>
+ <string>0.901961</string>
+ </dict>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Pattern</key>
+ <integer>1</integer>
+ </dict>
+ </dict>
+ </dict>
+ <dict>
+ <key>Bounds</key>
+ <string>{{180, 144}, {36, 36}}</string>
+ <key>Class</key>
+ <string>ShapedGraphic</string>
+ <key>ID</key>
+ <integer>8</integer>
+ <key>Shape</key>
+ <string>Rectangle</string>
+ <key>Style</key>
+ <dict>
+ <key>fill</key>
+ <dict>
+ <key>Color</key>
+ <dict>
+ <key>b</key>
+ <string>0.901961</string>
+ <key>g</key>
+ <string>0.901961</string>
+ <key>r</key>
+ <string>0.901961</string>
+ </dict>
+ </dict>
+ <key>shadow</key>
+ <dict>
+ <key>Draws</key>
+ <string>NO</string>
+ </dict>
+ <key>stroke</key>
+ <dict>
+ <key>Pattern</key>
+ <integer>1</integer>
+ </dict>
+ </dict>
+ </dict>
+ </array>
+ <key>GridInfo</key>
+ <dict/>
+ <key>GuidesLocked</key>
+ <string>NO</string>
+ <key>GuidesVisible</key>
+ <string>YES</string>
+ <key>HPages</key>
+ <integer>1</integer>
+ <key>ImageCounter</key>
+ <integer>1</integer>
+ <key>KeepToScale</key>
+ <false/>
+ <key>Layers</key>
+ <array>
+ <dict>
+ <key>Lock</key>
+ <string>NO</string>
+ <key>Name</key>
+ <string>Layer 1</string>
+ <key>Print</key>
+ <string>YES</string>
+ <key>View</key>
+ <string>YES</string>
+ </dict>
+ </array>
+ <key>LayoutInfo</key>
+ <dict>
+ <key>Animate</key>
+ <string>NO</string>
+ <key>circoMinDist</key>
+ <real>18</real>
+ <key>circoSeparation</key>
+ <real>0.0</real>
+ <key>layoutEngine</key>
+ <string>dot</string>
+ <key>neatoSeparation</key>
+ <real>0.0</real>
+ <key>twopiSeparation</key>
+ <real>0.0</real>
+ </dict>
+ <key>LinksVisible</key>
+ <string>NO</string>
+ <key>MagnetsVisible</key>
+ <string>NO</string>
+ <key>MasterSheets</key>
+ <array/>
+ <key>ModificationDate</key>
+ <string>2015-12-16 20:32:49 +0000</string>
+ <key>Modifier</key>
+ <string>Heng Li</string>
+ <key>NotesVisible</key>
+ <string>NO</string>
+ <key>Orientation</key>
+ <integer>2</integer>
+ <key>OriginVisible</key>
+ <string>NO</string>
+ <key>PageBreaks</key>
+ <string>YES</string>
+ <key>PrintInfo</key>
+ <dict>
+ <key>NSBottomMargin</key>
+ <array>
+ <string>float</string>
+ <string>41</string>
+ </array>
+ <key>NSHorizonalPagination</key>
+ <array>
+ <string>coded</string>
+ <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string>
+ </array>
+ <key>NSLeftMargin</key>
+ <array>
+ <string>float</string>
+ <string>18</string>
+ </array>
+ <key>NSPaperSize</key>
+ <array>
+ <string>size</string>
+ <string>{612, 792}</string>
+ </array>
+ <key>NSPrintReverseOrientation</key>
+ <array>
+ <string>int</string>
+ <string>0</string>
+ </array>
+ <key>NSRightMargin</key>
+ <array>
+ <string>float</string>
+ <string>18</string>
+ </array>
+ <key>NSTopMargin</key>
+ <array>
+ <string>float</string>
+ <string>18</string>
+ </array>
+ </dict>
+ <key>PrintOnePage</key>
+ <false/>
+ <key>ReadOnly</key>
+ <string>NO</string>
+ <key>RowAlign</key>
+ <integer>1</integer>
+ <key>RowSpacing</key>
+ <real>36</real>
+ <key>SheetTitle</key>
+ <string>Canvas 1</string>
+ <key>SmartAlignmentGuidesActive</key>
+ <string>YES</string>
+ <key>SmartDistanceGuidesActive</key>
+ <string>YES</string>
+ <key>UniqueID</key>
+ <integer>1</integer>
+ <key>UseEntirePage</key>
+ <false/>
+ <key>VPages</key>
+ <integer>1</integer>
+ <key>WindowInfo</key>
+ <dict>
+ <key>CurrentSheet</key>
+ <integer>0</integer>
+ <key>ExpandedCanvases</key>
+ <array>
+ <dict>
+ <key>name</key>
+ <string>Canvas 1</string>
+ </dict>
+ </array>
+ <key>Frame</key>
+ <string>{{367, 6}, {710, 872}}</string>
+ <key>ListView</key>
+ <true/>
+ <key>OutlineWidth</key>
+ <integer>142</integer>
+ <key>RightSidebar</key>
+ <false/>
+ <key>ShowRuler</key>
+ <true/>
+ <key>Sidebar</key>
+ <true/>
+ <key>SidebarWidth</key>
+ <integer>120</integer>
+ <key>VisibleRegion</key>
+ <string>{{0, 0}, {575, 733}}</string>
+ <key>Zoom</key>
+ <real>1</real>
+ <key>ZoomValues</key>
+ <array>
+ <array>
+ <string>Canvas 1</string>
+ <real>1</real>
+ <real>1</real>
+ </array>
+ </array>
+ </dict>
+</dict>
+</plist>
diff --git a/tex/miniasm.bib b/tex/miniasm.bib
new file mode 100644
index 0000000..900f487
--- /dev/null
+++ b/tex/miniasm.bib
@@ -0,0 +1,256 @@
+@inproceedings{DBLP:conf/wabi/Myers14,
+ Author = {Gene Myers},
+ Booktitle = {Algorithms in Bioinformatics - 14th International Workshop, {WABI} 2014, Wroclaw, Poland, September 8-10, 2014. Proceedings},
+ Crossref = {DBLP:conf/wabi/2014},
+ Pages = {52--67},
+ Title = {Efficient Local Alignment Discovery amongst Noisy Long Reads},
+ Year = {2014}}
+
+@proceedings{DBLP:conf/wabi/2014,
+ Editor = {Daniel G. Brown and Burkhard Morgenstern},
+ Publisher = {Springer},
+ Title = {Algorithms in Bioinformatics - 14th International Workshop, {WABI} 2014, Wroclaw, Poland, September 8-10, 2014. Proceedings},
+ Volume = {8701},
+ Year = {2014}}
+
+@inproceedings{DBLP:conf/sigmod/SchleimerWA03,
+ Author = {Saul Schleimer and Daniel Shawcross Wilkerson and Alexander Aiken},
+ Booktitle = {Proceedings of the 2003 {ACM} {SIGMOD} International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003},
+ Crossref = {DBLP:conf/sigmod/2003},
+ Pages = {76--85},
+ Title = {Winnowing: Local Algorithms for Document Fingerprinting},
+ Year = {2003}}
+
+@proceedings{DBLP:conf/sigmod/2003,
+ Editor = {Alon Y. Halevy and Zachary G. Ives and AnHai Doan},
+ Publisher = {{ACM}},
+ Title = {Proceedings of the 2003 {ACM} {SIGMOD} International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003},
+ Year = {2003}}
+
+@article{Myers:2000kl,
+ Author = {Myers, E W and others},
+ Journal = {Science},
+ Pages = {2196-204},
+ Title = {A whole-genome assembly of {Drosophila}},
+ Volume = {287},
+ Year = {2000}}
+
+@article{Roberts:2004fv,
+ Author = {Roberts, Michael and others},
+ Journal = {Bioinformatics},
+ Pages = {3363-9},
+ Title = {Reducing storage requirements for biological sequence comparison},
+ Volume = {20},
+ Year = {2004}}
+
+@article{Myers:2005bh,
+ Author = {Myers, Eugene W},
+ Journal = {Bioinformatics},
+ Pages = {ii79-85},
+ Title = {The fragment assembly string graph},
+ Volume = {21 Suppl 2},
+ Year = {2005}}
+
+@article{Zerbino:2008uq,
+ Author = {Zerbino, Daniel R and Birney, Ewan},
+ Journal = {Genome Res},
+ Pages = {821-9},
+ Title = {Velvet: algorithms for de novo short read assembly using de {Bruijn} graphs},
+ Volume = {18},
+ Year = {2008}}
+
+@article{Kahn62aa,
+ Author = {Kahn, Arthur B},
+ Journal = {Communications of the ACM},
+ Pages = {558--562},
+ Title = {Topological sorting of large networks},
+ Volume = {5},
+ Year = {1962}}
+
+@article{Li:2012fk,
+ Author = {Li, Heng},
+ Journal = {Bioinformatics},
+ Pages = {1838-44},
+ Title = {Exploring single-sample {SNP} and {INDEL} calling with whole-genome de novo assembly},
+ Volume = {28},
+ Year = {2012}}
+
+@article{Berlin:2015xy,
+ Author = {Berlin, Konstantin and others},
+ Journal = {Nat Biotechnol},
+ Pages = {623-30},
+ Title = {Assembling large genomes with single-molecule sequencing and locality-sensitive hashing},
+ Volume = {33},
+ Year = {2015}}
+
+@article{sovic:2015aa,
+ Author = {Ivan Sovic and others},
+ Journal = {bioRxiv},
+ Title = {Fast and sensitive mapping of error-prone nanopore sequencing reads with GraphMap},
+ Year = {2015}}
+
+@article{TCS15,
+ author = {Ljiljana Brankovic and others},
+ title = {Linear-Time Superbubble Identification Algorithm for Genome Assembly},
+ journal = {Theoretical Computer Science},
+ year = {2015},
+ doi = {10.1016/j.tcs.2015.10.021}
+}
+
+@inproceedings{DBLP:conf/wabi/OnoderaSS13,
+ Author = {Taku Onodera and Kunihiko Sadakane and Tetsuo Shibuya},
+ Booktitle = {{WABI}},
+ Crossref = {DBLP:conf/wabi/2013},
+ Pages = {338--348},
+ Title = {Detecting Superbubbles in Assembly Graphs},
+ Year = {2013}}
+
+@proceedings{DBLP:conf/wabi/2013,
+ editor = {Aaron E. Darling and
+ Jens Stoye},
+ title = {Algorithms in Bioinformatics - 13th International Workshop, {WABI}
+ 2013, Sophia Antipolis, France, September 2-4, 2013. Proceedings},
+ series = {Lecture Notes in Computer Science},
+ volume = {8126},
+ publisher = {Springer},
+ year = {2013},
+}
+
+@article{Wick:2015qf,
+ Author = {Wick, Ryan R and others},
+ Journal = {Bioinformatics},
+ Pages = {3350-2},
+ Title = {Bandage: interactive visualization of de novo genome assemblies},
+ Volume = {31},
+ Year = {2015}}
+
+@article{Li:2009ys,
+ Author = {Li, Heng and others},
+ Journal = {Bioinformatics},
+ Pages = {2078-9},
+ Title = {The Sequence Alignment/Map format and SAMtools},
+ Volume = {25},
+ Year = {2009}}
+
+@article{Alkan:2011zr,
+ Author = {Alkan, Can and others},
+ Journal = {Nat Methods},
+ Pages = {61-5},
+ Title = {Limitations of next-generation genome sequence assembly},
+ Volume = {8},
+ Year = {2011}}
+
+@article{Chaisson:2015wj,
+ Author = {Chaisson, Mark J P and others},
+ Journal = {Nat Rev Genet},
+ Pages = {627-40},
+ Title = {Genetic variation and the de novo assembly of human genomes},
+ Volume = {16},
+ Year = {2015}}
+
+@article{Bashir:2012gb,
+ Author = {Bashir, Ali and others},
+ Journal = {Nat Biotechnol},
+ Pages = {701-7},
+ Title = {A hybrid approach for the automated finishing of bacterial genomes},
+ Volume = {30},
+ Year = {2012}}
+
+@article{Ribeiro:2012bx,
+ Author = {Ribeiro, Filipe J and others},
+ Journal = {Genome Res},
+ Pages = {2270-7},
+ Title = {Finished bacterial genomes from shotgun sequence data},
+ Volume = {22},
+ Year = {2012}}
+
+@article{Koren:2012pt,
+ Author = {Koren, Sergey and others},
+ Journal = {Nat Biotechnol},
+ Pages = {693-700},
+ Title = {Hybrid error correction and de novo assembly of single-molecule sequencing reads},
+ Volume = {30},
+ Year = {2012}}
+
+@article{Chin:2013qr,
+ Author = {Chin, Chen-Shan and others},
+ Journal = {Nat Methods},
+ Pages = {563-9},
+ Title = {Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data},
+ Volume = {10},
+ Year = {2013}}
+
+@article{Koren:2013fc,
+ Author = {Koren, Sergey and others},
+ Journal = {Genome Biol},
+ Pages = {R101},
+ Title = {Reducing assembly complexity of microbial genomes with single-molecule sequencing},
+ Volume = {14},
+ Year = {2013}}
+
+@article{Quick:2014uf,
+ Author = {Quick, Joshua and others},
+ Journal = {Gigascience},
+ Pages = {22},
+ Title = {A reference bacterial genome dataset generated on the MinION{\texttrademark} portable single-molecule nanopore sequencer},
+ Volume = {3},
+ Year = {2014}}
+
+@article{Loman:2015xu,
+ Author = {Loman, Nicholas J and others},
+ Journal = {Nat Methods},
+ Pages = {733-5},
+ Title = {A complete bacterial genome assembled de novo using only nanopore sequencing data},
+ Volume = {12},
+ Year = {2015}}
+
+@article{Chaisson:2012aa,
+ Author = {Chaisson, Mark J and Tesler, Glenn},
+ Journal = {BMC Bioinformatics},
+ Pages = {238},
+ Title = {Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory},
+ Volume = {13},
+ Year = {2012}}
+
+@inproceedings{Broder:1997aa,
+ Author = {Broder, Andrei Z},
+ Booktitle = {Compression and Complexity of Sequences},
+ Pages = {21-29},
+ Title = {On the resemblance and containment of documents},
+ Year = {1997}}
+
+@article{Altschul:1997vn,
+ Author = {Altschul, S F and others},
+ Journal = {Nucleic Acids Res},
+ Pages = {3389-402},
+ Title = {Gapped {BLAST} and {PSI-BLAST}: a new generation of protein database search programs},
+ Volume = {25},
+ Year = {1997}}
+
+@article{Kent:2002jk,
+ Author = {Kent, W James},
+ Journal = {Genome Res},
+ Pages = {656-64},
+ Title = {{BLAT}--the {BLAST}-like alignment tool},
+ Volume = {12},
+ Year = {2002}}
+
+@phdthesis{harris:2007aa,
+ Author = {Harris, R.S.},
+ School = {The Pennsylvania State University},
+ Title = {Improved pairwise alignment of genomic DNA},
+ Year = {2007}}
+
+@article{Kiebasa:2011aa,
+ Author = {Kie{\l}basa, Szymon M and others},
+ Journal = {Genome Res},
+ Pages = {487-93},
+ Title = {Adaptive seeds tame genomic sequence comparison},
+ Volume = {21},
+ Year = {2011}}
+
+@article{Li:2013aa,
+ Author = {Li, Heng},
+ Journal = {arXiv:1303.3997},
+ Title = {Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM},
+ Year = {2013}}
diff --git a/tex/miniasm.tex b/tex/miniasm.tex
new file mode 100644
index 0000000..5da22f0
--- /dev/null
+++ b/tex/miniasm.tex
@@ -0,0 +1,862 @@
+\documentclass{bioinfo}
+\copyrightyear{2015}
+\pubyear{2015}
+
+\usepackage{amsmath}
+\usepackage[ruled,vlined]{algorithm2e}
+\newcommand\mycommfont[1]{\footnotesize\rmfamily{\it #1}}
+\SetCommentSty{mycommfont}
+\SetKwComment{Comment}{$\triangleright$\ }{}
+
+\usepackage{natbib}
+\bibliographystyle{apalike}
+
+\begin{document}
+\firstpage{1}
+
+\title[Long-read mapping and assembly]{Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences}
+\author[Li]{Heng Li}
+\address{Broad Institute, 75 Ames Street, Cambridge, MA 02142, USA}
+\maketitle
+
+\begin{abstract}
+
+\section{Motivation:} Single Molecule Real-Time (SMRT) sequencing technology and Oxford
+Nanopore technologies (ONT) produce reads over 10kbp in length, which have
+enabled high-quality genome assembly at an affordable cost. However, at
+present, long reads have an error rate as high as 10--15\%. Complex and
+computationally intensive pipelines are required to assemble such reads.
+
+\section{Results:} We present a new mapper, minimap, and a \emph{de novo}
+assembler, miniasm, for efficiently mapping and assembling SMRT and ONT reads
+without an error correction stage. They can often assemble a sequencing run of
+bacterial data into a single contig in a few minutes, and assemble 45-fold
+\emph{C. elegans} data in 9 minutes, orders of magnitude faster than the
+existing pipelines, though the consensus sequence error rate is as high as raw
+reads. We also introduce a pairwise read mapping format (PAF) and
+a graphical fragment assembly format (GFA), and demonstrate the
+interoperability between ours and current tools.
+
+\section{Availability and implementation:} https://github.com/lh3/minimap and
+https://github.com/lh3/miniasm
+
+\section{Contact:} hengli@broadinstitute.org
+
+\end{abstract}
+
+\section{Introduction}
+
+High-throughput short-read sequencing technologies, such as Illumina, have
+empowered a variety of biological researches and clinical applications that
+would not be practical with the older Sanger sequencing. However, the short
+read length (typically a few hundred basepairs) has posed a great challenge to
+\emph{de novo} assembly as many repetitive sequences and segmental duplications
+are longer than the read length and can hardly be resolved by short reads even
+with paired-end data~\citep{Alkan:2011zr}. Although with increased read length
+and improved algorithms we are now able to produce much better short-read
+assemblies than a few years ago, the contiguity and completeness of the
+assemblies are still not as good as Sanger assemblies~\citep{Chaisson:2015wj}.
+
+The PacBio's SMRT technology were developed partly as an answer to the
+problem with short-read \emph{de novo} assembly. However, due to the high
+per-base error rate, around 15\%, these reads were only used as a complement to
+short reads initially~\citep{Bashir:2012gb,Ribeiro:2012bx,Koren:2012pt},
+until~\citet{Chin:2013qr} and~\citet{Koren:2013fc} demonstrated the feasibility
+of SMRT-only assembly. Since then, SMRT is becoming the preferred technology
+for finishing small genomes and producing high-quality Eukaryotic
+genomes~\citep{Berlin:2015xy}.
+
+Oxford Nanopore Technologies (ONT) has recently offered another long-read
+sequencing technology. Although the per-base error rate was high at the
+early access phase~\citep{Quick:2014uf}, the latest data quality has been
+greatly improved. \citet{Loman:2015xu} confirmed that we can achieve
+high-quality bacterial assembly with ONT data alone.
+
+Published long-read assembly pipelines all include four stages: (i) all-vs-all
+raw read mapping, (ii) raw read error correction, (iii) assembly of error
+corrected reads and (iv) contig consensus polish. Stage (iii) may involve
+all-vs-all read mapping again, but as the error rate is much reduced at this
+step, it is easier and faster than stage (i). Table~\ref{tab:tools} shows the tools used for
+each stage. Notably, our tool minimap is a raw read overlapper and miniasm is
+an assembler. We do not correct sequencing errors, but instead directly produce
+unpolished and uncorrected contig sequences from raw read overlaps. The idea of
+correction-free assembly was inspired by talks given by Gene Myers.
+Sikic et al (personal communication) are also independently exploring such an
+approach.
+
+\begin{table}[b]
+\processtable{Tools for noisy long-read assembly}
+{\footnotesize\label{tab:tools}
+\begin{tabular}{p{2.4cm}p{2cm}l}
+\toprule
+Functionality & Program & Reference \\
+\midrule
+Raw read overlap & BLASR & \citet{Chaisson:2012aa}\\
+& DALIGNER & \citet{DBLP:conf/wabi/Myers14} \\
+& MHAP & \citet{Berlin:2015xy} \\
+& GraphMap & \citet{sovic:2015aa} \\
+& minimap & this article \\
+Error correction & pbdagcon & http://bit.ly/pbdagcon \\
+& falcon\_sense & http://bit.ly/pbfcasm \\
+& nanocorrect & \citet{Loman:2015xu} \\
+Assembly & wgs-assembler & \citet{Myers:2000kl} \\
+& Falcon & http://bit.ly/pbfcasm \\
+& ra-integrate & http://bit.ly/raitgasm \\
+& miniasm & this article \\
+Consensus polish & Quiver & http://bit.ly/pbquiver \\
+& nanopolish & \citet{Loman:2015xu} \\
+\botrule
+\end{tabular}
+}{}
+\end{table}
+
+As we can see from Table~\ref{tab:tools}, each stage can be achieved with multiple tools.
+Although we have successfully combined tools into different pipelines, we
+need to change or convert the input/output formats to make them work
+together. Another contribution of this article is the proposal of concise
+mapping and assembly formats, which will hopefully encourage modular design of
+assemblers and the associated tools.
+
+\begin{methods}
+\section{Methods}
+
+\subsection{General notations}
+
+Let $\Sigma=\{\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{T}\}$ be the
+alphabet of nucleotides. For a symbol $a\in\Sigma$, $\overline{a}$ is the
+Watson-Crick complement of $a$. A string $s=a_1a_2\cdots a_n$ over
+$\Sigma$ is also called a \emph{DNA sequence}. Its length is $|s|=n$;
+its \emph{reverse complement} is $\overline{s}=\overline{a_1a_2\cdots
+a_n}=\overline{a}_n\overline{a}_{n-1}\cdots\overline{a}_1$.
+For convenience, we define strand function
+$\pi:\Sigma^*\times\{0,1\}\to\Sigma^*$ such that $\pi(s,0)=s$ and
+$\pi(s,1)=\overline{s}$. Here $\Sigma^*$ is the set of all DNA sequences.
+
+By convention, we call a $k$-long DNA sequence as a \emph{$k$-mer}. We use the
+notation $s^k_i=a_i\cdots a_{i+k-1}$ to denote a $k$-long substring of $s$
+starting at $i$. $\Sigma^k$ is the set of all $k$-mers.
+
+\subsection{Minimap}
+
+\subsubsection{Overview of $k$-mer based sequence similarity search}\label{sec:minimapov}
+
+BLAST~\citep{Altschul:1997vn} and BLAT~\citep{Kent:2002jk} are among the most
+popular sequence similarity search tools. They use one $k$-mer hash function
+$\phi:\Sigma^k\to\mathbb{Z}$ to hash $k$-mers at the positions
+$1,w+1,2w+1,\ldots$ of a target sequence and keep the hash values in a hash
+table. Upon query, they use the same hash function on every $k$-mer of the
+query sequence and look up the hash table for potential matches. If there are
+one or multiple $k$-mer matches in a small window, these aligners extend the
+matches with dynamic programming to construct the final alignment.
+
+DALIGNER~\citep{DBLP:conf/wabi/Myers14} does not use a hash table. It instead
+identifies $k$-mer matches between two sets of reads by sorting $k$-mers and
+merging the sorted lists. DALIGNER is fast primarily because sorting and
+merging are highly cache efficient.
+
+MHAP~\citep{Berlin:2015xy} differs from others in the use of MinHash
+sketch~\citep{Broder:1997aa}. Briefly, given a read sequence $s$ and $m$
+$k$-mer hash functions $\{\phi_j\}_{1\le j\le m}$, MHAP computes
+$h_j=\min\{\phi_j(s_i^k):1\le i\le |s|-k+1\}$ with each hash function $\phi_j$, and
+takes list $(h_j)_{1\le j\le m}$, which is called the \emph{sketch} of
+$s$, as a reduced representation of $s$. Suppose $(h_j)_j$ and $(h'_j)_j$ are
+the sketches of two reads, respectively. When the two reads are similar to each
+other or have significant overlaps, there are likely to exist multiple $j$ such
+that $h_j=h'_j$. Potential matches can thus be identified. A limitation of
+MinHash sketch is that it always selects a fixed number of hash values
+regardless of the length of the sequences. This may waste space or hurt
+sensitivity when input sequences vary greatly in lengths.
+
+Minimap is heavily influenced by all these works. It adopts the idea of sketch
+like MHAP but takes minimizers \citep{DBLP:conf/sigmod/SchleimerWA03,Roberts:2004fv} as a reduced
+representation instead; it stores $k$-mers in a hash table like BLAT and MHAP
+but also uses sorting extensively like DALIGNER. In addition, minimap is
+designed not only as a read overlapper but also as a read-to-genome and
+genome-to-genome mapper. It has more potential applications.
+
+\subsubsection{Computing minimizers}
+
+\begin{algorithm}[tb]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{Parameter $w$ and $k$ and sequence $s$ with $|s|\ge w+k-1$}
+\KwOut{($w$,$k$)-minimizers, their positions and strands}
+\BlankLine
+\textbf{Function} {\sc MinimizerSketch}$(s,w,k)$
+\Begin {
+ $\mathcal{M}\gets\emptyset$\Comment*[r]{NB: $\mathcal{M}$ is a set; no duplicates}
+ \For{$i\gets1$ \KwTo $|s|-w-k+1$} {
+ $m\gets\infty$\;
+ \nl\For (\Comment*[f]{Find the min value}) {$j\gets0$ \KwTo $w-1$} {
+ $(u,v)\gets(\phi(s^k_{i+j}),\phi(\overline{s}^k_{i+j}))$\;
+ \If (\Comment*[f]{Skip if strand ambiguous}) {$u\not=v$} {
+ $m\gets\min(m,\min(u,v))$\;
+ }
+ }
+ \nl\For (\Comment*[f]{Collect minimizers}) {$j\gets0$ \KwTo $w-1$} {
+ $(u,v)\gets(\phi(s^k_{i+j}),\phi(\overline{s}^k_{i+j}))$\;
+ \uIf{$u<v$ {\bf and} $u=m$} {
+ $\mathcal{M}\gets\mathcal{M}\cup\{(m,i+j,0)\}$\;
+ }\ElseIf{$v<u$ {\bf and} $v=m$}{
+ $\mathcal{M}\gets\mathcal{M}\cup\{(m,i+j,1)\}$\;
+ }
+ }
+ }
+ \Return $M$\;
+}
+\caption{Compute minimizers}\label{alg:minimizer}
+\end{algorithm}
+
+Loosely speaking, a $(w,k)$-minimizer of a string is the
+smallest $k$-mer in a surrounding window of $w$ consecutive $k$-mers. Formally,
+let $\phi:\Sigma^k\to\mathbb{Z}$ be a $k$-mer hash function.
+A \emph{double-strand $(w,k,\phi)$-minimizer}, or simply a \emph{minimizer}, of a
+string $s$, $|s|\ge w+k-1$, is a triple $(h,i,r)$ such that there exists
+$\max(1,i-w+1)\le j\le\min(i,|s|-w-k+1)$ which renders
+$$
+h=\phi(\pi(s_i^k,r))=\min\big\{\phi(\pi(s_{j+p}^k,r')):0\le p<w,r'\in\{0,1\}\big\}
+$$
+Let $\mathcal{M}(s)$ be the set of minimizers of $s$. Algorithm~\ref{alg:minimizer} gives the
+pseudocode to compute $\mathcal{M}(s)$ in $O(w\cdot|s|)$ time. Our actual
+implementation is close to $O(|s|)$ in average case. It uses a queue to cache
+the previous minimals and avoids the loops at line~1 and~2 most of time. In
+practice, time spent on collecting minimizers is insignificant.
+
+A natural choice of hash function $\phi$ is to let $\phi(\mathrm{A})=0$,
+$\phi(\mathrm{C})=1$, $\phi(\mathrm{G})=2$ and $\phi(\mathrm{T})=3$ and for a
+$k$-mer $s=a_1\cdots a_k$, define
+$$
+\phi(s)=\phi(a_1)\times4^{k-1}+\phi(a_2)\times4^{k-2}+\cdots+\phi(a_k)
+$$
+This hash function always maps a $k$-mer to a distinct $2k$-bit integer. A
+problem with this $\phi$ is that poly-A, which is often highly enriched in
+genomes, always gets zero, the smallest value. We may oversample these
+non-informative poly-A and hurt practical performance. To alleviate this issue,
+we use function $\phi'=h\circ\phi$ instead, where $h$ is an invertible integer
+hash function on $[0,4^k)$ (Algorithm~\ref{alg:invhash}; http://bit.ly/invihgi). The
+invertibility of $h$ is not essential, but as such $\phi'$ never maps two
+distinct $k$-mers to the same $2k$-bit integer, it helps to reduce hash
+collisions.
+
+\begin{algorithm}[tb]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{$p$-bit integer $x$}
+\KwOut{hashed $p$-bit integer}
+\BlankLine
+\textbf{Function} {\sc InvertibleHash}$(x,p)$
+\Begin {
+ $m\gets2^p-1$\;
+ $x\gets(\mbox{\tt\char126}x+(x\mbox{\tt\char60\char60}21))\mbox{ \tt\char38}\mbox{ }m$\;
+ $x\gets x\mbox{ \tt\char94}\mbox{ }x\mbox{\tt\char62\char62}24$\;
+ $x\gets(x+(x\mbox{\tt\char60\char60}3)+(x\mbox{\tt\char60\char60}8))\mbox{ \tt\char38}\mbox{ }m$\;
+ $x\gets x\mbox{ \tt\char94}\mbox{ }x\mbox{\tt\char62\char62}14$\;
+ $x\gets(x+(x\mbox{\tt\char60\char60}2)+(x\mbox{\tt\char60\char60}4))\mbox{ \tt\char38}\mbox{ }m$\;
+ $x\gets x\mbox{ \tt\char94}\mbox{ }x\mbox{\tt\char62\char62}28$\;
+ $x\gets(x+(x\mbox{\tt\char60\char60}31))\mbox{ \tt\char38}\mbox{ }m$\;
+ \Return $x$\;
+}
+\caption{Invertible integer hash function}\label{alg:invhash}
+\end{algorithm}
+
+Note that in a window of $w$ consecutive $k$-mers, there may be more than one
+minimizers. Algorithm~\ref{alg:minimizer} keeps them all with the loop at line~2. This way, a
+minimizer of $s$ always corresponds to a minimizer of $\overline{s}$.
+
+For read overlapping, we use $k=15$ and $w=5$ to find minimizers.
+
+\subsubsection{Indexing}
+
+\begin{algorithm}[tb]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{Set of target sequences $\mathcal{T}=\{s_1,\ldots,s_T\}$}
+\KwOut{Minimizer hash table $\mathcal{H}$}
+\BlankLine
+\textbf{Function} {\sc Index}$(\mathcal{T},w,k)$
+\Begin {
+ $\mathcal{H}\gets$ empty hash table\;
+ \For{$t\gets1$ \KwTo $T$} {
+ $\mathcal{M}\gets${\sc MinimizerSketch}$(s_t,w,k)$\;
+ \ForEach{$(h,i,r)\in \mathcal{M}$} {
+ $\mathcal{H}[h]\gets\mathcal{H}[h]\cup\{(t,i,r)\}$\;
+ }
+ }
+ \Return $\mathcal{H}$\;
+}
+\caption{Index target sequences}\label{alg:idx}
+\end{algorithm}
+
+Algorithm~\ref{alg:idx} describes indexing target sequences. It keeps minimizers of all target
+sequences in a hash table where the key is the minimizer hash and the value is
+a set of target sequence index, the position of the minimizer and the strand
+(packed into one 64-bit integer).
+
+In implementation, we do not directly insert minimizers to the hash table.
+Instead, we append minimizers to an array of two 64-bit integers (one for minimizer sequence and one for position) and sort the array after collecting
+all minimizers. The hash table keeps the intervals on the sorted array. This
+procedure dramatically reduces heap allocations and cache misses, and is
+supposedly faster than direct hash table insertion.
+
+\subsubsection{Mapping}
+
+Given two sequences $s$ and $s'$, we say we find a \emph{minimizer hit}
+$(h,x,i,i')$ if there exist $(h,i,r)\in\mathcal{M}(s)$ and
+$(h,i',r')\in\mathcal{M}(s')$ with $x=r\oplus r'$ ($\oplus$ is the XOR
+operator). Here $h$ is the minimizer hash value, $x$ indicates the relative
+strand and $i$ and $i'$ are the positions on the two sequences, respectively.
+We say two minimizer hits $(h_1,x,i_1,i'_1)$ and $(h_2,x,i_2,i'_2)$ are
+\emph{$\epsilon$-away} if 1) $x=0$ and $|(i_1-i'_1)-(i_2-i'_2)|<\epsilon$
+or 2) $x=1$ and $|(i_1+i'_1)-(i_2+i'_2)|<\epsilon$. Intuitively,
+$\epsilon$-away hits are approximately colinear within a band of width
+$\epsilon$ (500bp by default). Given a set of minimizer hits $\{(h,x,i,i')\}$, we can cluster
+$i-i'$ for $x=0$ or $i+i'$ for $x=1$ to identify long colinear matches.
+This procedure is inspired by Hough Transformation mentioned
+by~\citet{sovic:2015aa}.
+
+\begin{algorithm}[tb]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{Hash table $\mathcal{H}$ and query sequence $q$}
+\KwOut{Print matching query and target intervals}
+\BlankLine
+\textbf{Function} {\sc Map}$(\mathcal{H},q,w,k,\epsilon)$
+\Begin {
+ $\mathcal{A}\gets$ empty array\;
+ $\mathcal{M}\gets${\sc MinimizerSketch}$(q,w,k)$\;
+ \nl\ForEach (\Comment*[f]{Collect minimizer hits}) {$(h,i,r)\in \mathcal{M}$} {
+ \ForEach{$(t,i',r')\in \mathcal{H}[h]$} {
+ \uIf (\Comment*[f]{Minimizers on the same strand}) {$r=r'$} {
+ Append $(t,0,i-i',i')$ to $\mathcal{A}$\;
+ } \Else (\Comment*[f]{On different strands}) {
+ Append $(t,1,i+i',i')$ to $\mathcal{A}$\;
+ }
+ }
+ }
+ Sort $\mathcal{A}=[(t,r,c,i')]$ in the order of the four values in tuples\;
+ $b\gets1$\;
+ \nl\For (\Comment*[f]{Cluster minimizer hits}) {$e=1$ \KwTo $|\mathcal{A}|$} {
+ \If{$e=|\mathcal{A}|$ {\bf or} $\mathcal{A}[e+1].t\not=\mathcal{A}[e].t$ {\bf or} $\mathcal{A}[e+1].r\not=\mathcal{A}[e].r$ {\bf or} $\mathcal{A}[e+1].c-\mathcal{A}[e].c\ge\epsilon$} {
+ \nl$\mathcal{C}\gets$ the maximal colinear subset of $\mathcal{A}[b..e]$\;
+ Print the left- and right-most query/target positions in $\mathcal{C}$\;
+ $b\gets e+1$\;
+ }
+ }
+}
+\caption{Map a query sequence}\label{alg:map}
+\end{algorithm}
+
+Algorithm~\ref{alg:map} gives the details of the mapping algorithm. The loop at line~1
+collects minimizer hits between the query and all the target sequences. The
+loop at line~2 performs a single-linkage clustering to group approximately
+colinear hits. Some hits in a cluster may not be colinear because two minimizer
+hits within distance $\epsilon$ are always $\epsilon$-away. To fix this issue,
+we find the maximal colinear subset of hits by solving a longest increasing
+sequencing problem (line~3). This subset is the final mapping result. In
+practical implementation, we set thresholds on the size of the subset (4 by
+default) and the number of matching bases in the subset to filter poor mappings
+(100 for read overlapping).
+
+\subsection{Assembly graph}
+
+Two strings $v$ and $w$ may be mapped to each other based on their sequence
+similarity. If $v$ can be mapped to a substring of $w$, we say $w$
+\emph{contains} $v$. If a suffix of $v$ and a prefix of $w$ can be mapped to
+each other, we say $v$ \emph{overlaps} $w$, written as $v\to w$.
+If we regard strings $v$ and $w$ as vertices, the overlap relationship defines
+a directed edge between them. The \emph{length} of $v\to w$ equals the length
+of $v$'s prefix that is not in the prefix-suffix match.
+
+Let $G=(V,E,\ell)$ be a graph without multi-edges, where $V$ is a
+set of DNA sequences (vertices), $E$ a set of overlaps between them (edges) and
+$\ell:E\to\Re_+$ is the edge length function. $G$ is said to be
+\emph{Watson-Crick complete} if i) $\forall v\in V$, $\overline{v}\in V$ and
+ii) $\forall v\to w\in E$, $\overline{w}\to\overline{v}\in E$. $G$ is said to
+be \emph{containment-free} if any sequence $v$ is not contained in other
+sequences in $V$. If $G$ is both Watson-Crick complete and containment-free, it
+is an \emph{assembly graph}. By definition, any vertex $v$ has a
+\emph{complement vertex} $\overline{v}$ in the graph and any edge $v\to w$ has
+a \emph{complement edge} $\overline{w}\to\overline{v}$. Let
+$\mathrm{deg}^+(v)$ be the outdegree of $v$ and $\mathrm{deg}^-(v)$ be the
+indegree. It follows that $\mathrm{deg}^-(v)=\mathrm{deg}^+(\overline{v})$.
+
+An assembly graph has the same topology as a string graph~\citep{Myers:2005bh},
+though the interpretation of the vertex set $V$ is different. In a string
+graph, $V$ is the set of the two ends of sequences, not the set of forward and
+reverse-complemented sequences. De Bruijn graph can be regarded as a special
+case of overlap graph. It is also an assembly graph.
+
+In an assembly graph, an edge $v\to w$ is \emph{transitive} if there exist
+$v\to u$ and $u\to w$. Removing a transitive edge does not affect the
+connectivity of the graph. A vertex $v$ is a \emph{tip} if ${\rm deg}^+(v)=0$
+and ${\rm deg}^-(v)>0$. The majority of tips are caused by artifacts or missing
+overlaps. A \emph{bubble} is a directed acyclic subgraph with a single source
+$v$ and a single sink $w$ having at least two paths between $v$ and $w$, and without connecting the rest of the graph. The
+bubble is tight if ${\rm deg}^+(v)>1$ and ${\rm deg}^-(w)>1$. A bubble may be
+caused by missing overlaps or by variants between haplotypes in multi-ploidy samples or paralogs.
+It is preferred to collapse bubbles for high contiguity, though this introduces loss of information.
+
+\subsection{Miniasm}
+
+\subsubsection{Trimming reads}
+
+Raw read sequences may contain artifacts such as untrimmed adapters and
+chimaera. The first step of assembly to reduce such artifacts by examining
+read-to-read mappings. For each read, miniasm computes per-base coverage based
+on good mappings against other reads (longer than 2000bp with at least
+100bp non-redundant bases on matching minimizers). It then identifies the
+longest region having coverage three or more, and trims bases outside this
+region.
+
+\subsubsection{Generating assembly graph}
+
+\begin{figure}[tb]
+\centering
+\includegraphics[width=.45\textwidth]{overhang}
+\caption{Mapping between two reads. $b[1]$ and $e[1]$ are the 0-based starting and
+ending mapping coordinates of the first read $v$, respectively. $b[2]$ and
+$e[2]$ are the mapping coordinates of read $w$. Lightgray areas indicate
+overhang regions that should be mapped together if the overlap is real. If the
+overhang regions are small enough, the figure implies an edge $v\to w$ with
+approximate length $\ell(v\to w)=b[1]-b[2]$ and its complement edge
+$\overline{w}\to\overline{v}$ with
+$\ell(\overline{w}\to\overline{v})=(l[2]-e[2])-(l[1]-e[1])$.}\label{fig:overhang}
+\end{figure}
+
+\begin{algorithm}[bt]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{Read length $l$, mapping begin coordinate $b$ and mapping end $e$ of the
+two reads; max overhang length $o$ (1000 by default) and max overhang to mapping length ratio
+$r$ (0.8 by default).}
+\KwOut{hashed $p$-bit integer}
+\BlankLine
+\textbf{Function} {\sc ClassifyMapping}$(l[2], b[2], e[2], o, r)$
+\Begin {
+ ${\it overhang}\gets\min(b[1], b[2])+\min(l[1]-e[1],l[2]-e[2])$\;
+ ${\it maplen}\gets\max(e[1]-b[1],e[2]-b[2])$\;
+ \uIf{${\it overhang}>\min(o,{\it maplen}\cdot r)$} {
+ \Return {\tt INTERNAL\_MATCH}
+ } \uElseIf {$b[1]\le b[2]$ {\bf and} $l[1]-e[1]\le l[2]-e[2]$} {
+ \Return {\tt FIRST\_CONTAINED}
+ }\uElseIf {$b[1]\ge b[2]$ {\bf and} $l[1]-e[1]\ge l[2]-e[2]$} {
+ \Return {\tt SECOND\_CONTAINED}
+ } \uElseIf {$b[1]>b[2]$} {
+ \Return {\tt FIRST\_TO\_SECOND\_OVERLAP}
+ } \Else {
+ \Return {\tt SECOND\_TO\_FIRST\_OVERLAP}
+ }
+}
+\caption{Mapping classification}\label{alg:ovlp}
+\end{algorithm}
+
+For each trimmed mapping, miniasm applies Algorithm~\ref{alg:ovlp} to classify the mapping
+(see also Figure~\ref{fig:overhang} for the explanation of input variables).
+It ignores internal matches, drops contained reads and adds overlaps to the
+assembly graph. For a pair of reads, miniasm uses the longest overlap only to
+avoid multi-edges.
+
+
+\subsubsection{Graph cleaning}
+
+\begin{algorithm}[tb]
+\DontPrintSemicolon
+\footnotesize
+\KwIn{$G=(V,E)$, starting vertex $v_0$ and maximum probe distance $d$}
+\KwOut{the sink vertex of a bubble within $d$; or {\bf nil} if not found}
+\BlankLine
+\textbf{Function} {\sc DetectBubble}$(V,E,v_0,d)$
+\Begin {
+ \lIf{$\mathrm{deg}^+(v_0)<2$} { \Return {\bf nil} } \Comment*[r]{Not a source of bubble}
+ \lFor{$v\in V$} { $\delta[v]\gets\infty$ } \Comment*[r]{the min distance from $v_0$ to $v$}
+ $\delta[v_0]\gets0$\;
+ $S\gets$ empty stack \Comment*[r]{Vertices with all incoming edges visited}
+ {\sc Push}$(S,v_0)$\;
+ $p\gets0$ \Comment*[r]{Number of visited vertices never added to $S$}
+ \While{$S$ is not empty} {
+ $v\gets$ {\sc Pop}$(S)$\;
+ \ForEach{$v\to w\in E$} {
+ \If (\Comment*[f]{A circle involving the starting vertex}) {$w=v_0$} {
+ \Return {\bf nil}\;
+ }
+ \If (\Comment*[f]{Moving too far}) {$\delta[v]+\ell(v\to w)>d$} {
+ \Return {\bf nil}\;
+ }
+ \If (\Comment*[f]{Not visited before}) {$\delta[w]=\infty$} {
+ $\gamma[w]\gets \mathrm{deg}^-(w)$ \Comment*[r]{No. unvisited incoming edges}
+ $p\gets p+1$\;
+ }
+ \If{$\delta[v]+\ell(v\to w)<\delta[w]$} {
+ \nl$\delta[w]\gets \delta[v]+\ell(v\to w)$\;
+ }
+ $\gamma[w]\gets\gamma[w]-1$\;
+ \If (\Comment*[f]{All incoming edges visited}) {$\gamma[w]=0$} {
+ \If (\Comment*[f]{Not a tip}) {$\mathrm{deg}^+(w)\not=0$} {
+ {\sc Push}$(S,w)$\;
+ }
+ $p\gets p-1$\;
+ }
+ }
+ \If (\Comment*[f]{Found the sink}) {$|S|=1$ {\bf and} $p=0$} {
+ \Return {\sc Pop}$(S)$\;
+ }
+ }
+ \Return {\bf nil}\;
+}
+\caption{Bubble detection}\label{alg:popbub}
+\end{algorithm}
+
+After constructing the assembly graph, miniasm removes transitive
+edges~\citep{Myers:2005bh}, trims tipping unitigs composed of few reads (4 by default) and pops small
+bubbles~\citep{Zerbino:2008uq}. Algorithm~\ref{alg:popbub} detects bubbles where the longest path is shorter than $d$ (50kb by default). It is
+adapted from Kahn's topological sorting algorithm~\citep{Kahn62aa}. It starts
+from the potential source and visits a vertex when all its incoming edges are
+visited before. Algorithm~6 only detects bubbles. We can keep track of the
+optimal parent vertex at line~1 and then backtrack to collapse bubbles to a
+single path. Fermi~\citep{Li:2012fk} uses a similar algorithm except that it
+keeps two optimal paths through the bubble. \citet{DBLP:conf/wabi/OnoderaSS13}
+and \citet{TCS15} have also independently found similar algorithms.
+
+In addition, if $v\to w_1$ and $v\to w_2$ exist and $\ell(v\to w_1)<\ell(v\to
+w_2)$, miniasm removes $v\to w_2$ if $[|v|-\ell(v\to w_2)]/[|v|-\ell(v\to
+w_1)]$ is small enough (70\% by default). When there are longer overlaps,
+shorter overlaps after transitive reduction may be due to repeats.
+However, non-repetitive overlaps may also be removed at a small chance, which
+leads to missing overlaps and misassemblies.
+
+\subsubsection{Generating unitig sequences}
+
+If there are no multi-edges in the assembly graph, we can use $v_1\to
+v_2\to\cdots\to v_k$ to represent a path consisting of $k$ vertices. The
+sequence spelled from this path is the concatenation of vertex substrings:
+$v_1[1,\ell(v_1\to v_2)]\circ v_2[1,\ell(v_2\to v_3)]\circ\cdots\circ
+v_{k-1}[1,\ell(v_{k-1},v_k)]\circ v_k$, where $v[i,j]$ is the substring between
+$i$ and $j$ inclusive, and $\circ$ is the string concatenation operator.
+
+In a transitively reduced graph, a \emph{unitig}~\citep{Myers:2000kl} is a path $v_1\to
+v_2\to\cdots\to v_k$ such that ${\rm deg}^+(v_i)={\rm deg}^-(v_{i+1})=1$ and i)
+$v_1=v_k$ or ii) ${\rm deg}^-(v_1)\not=1$ and ${\rm deg}^+(v_k)\not=1$.
+Its sequence is the sequence spelled from the path. Intuitively, a unitig is a
+maximal path on which adjacent vertices can be ``unambiguously merged'' without
+affecting the connectivity of the original assembly graph.
+
+As miniasm does not correct sequencing errors, the error rate of unitig
+sequence is the same as the error rate of the raw input reads. It is in theory
+possible to derive a better unitig sequence by taking the advantage of read
+overlaps. We have not implemented such a consensus tool yet.
+
+\subsection{Formats: PAF and GFA}
+
+\subsubsection{Pairing mapping format (PAF)}
+
+\begin{table}[tb]
+\processtable{Pairwise mapping format (PAF)}
+{\footnotesize\label{tab:paf}
+\begin{tabular}{rcl}
+\toprule
+Col & Type & Description \\
+\midrule
+1 & string & Query sequence name \\
+2 & int & Query sequence length \\
+3 & int & Query start coordinate (BED-like) \\
+4 & int & Query end coordinate (BED-like) \\
+5 & char & `+' if query and target on the same strand; `-' if opposite \\
+6 & string & Target sequence name \\
+7 & int & Target sequence length \\
+8 & int & Target start coordinate on the original strand \\
+9 & int & Target end coordinate on the original strand \\
+10& int & Number of matching bases in the mapping \\
+11& int & Number bases, including gaps, in the mapping \\
+12& int & Mapping quality (0--255 with 255 for missing) \\
+\botrule
+\end{tabular}
+}{PAF is TAB-delimited text format with each line consisting of the above fixed
+fields. When the alignment is available, column 11 equals the total number of
+sequence matches, mismatches and gaps in the alignment. Column 10 divided by
+column 11 gives the alignment identity. If the detailed alignment is not
+available, column 10 and 11 can be approximate. PAF may optionally have
+additional fields in the SAM-like typed key-value format~\citep{Li:2009ys}.}
+\end{table}
+
+PAF is a lightweight format keeping the key mapping information (Table~\ref{tab:paf}).
+Minimap outputs mappings in PAF, which are taken by miniasm as input for
+assembly. We also provide scripts to convert DALIGNER, MHAP and SAM formats to
+PAF.
+
+\subsubsection{Graphical fragment assembly format (GFA)}
+
+\begin{table}[tb]
+\processtable{Graphical fragment assembly format (GFA)}
+{\footnotesize\label{tab:gfa}
+\begin{tabular}{clp{5.8cm}}
+\toprule
+Line & Comment & Fixed fields \\
+\midrule
+H & Header & N/A \\
+S & Segment & segName,segSeq \\
+L & Overlap & segName1,segOri1,segName2,segOri2,CIGAR \\
+\botrule
+\end{tabular}
+}{GFA is a line-based TAB-delimited format. Each line starts with a single
+letter determining the interpretation of the following TAB-delimited fields. In
+GFA, segment refers to a read or a unitig. A line start with `S' gives the name
+and sequence of a segment. When the sequence is not available, it can be a star
+`*'. Overlaps between segments are represented in lines starting with `L',
+giving the names and orientations of the two segments in an overlap. The last
+field `CIGAR' on an `L'-line describes the detailed alignment of the overlap if
+available. In addition to the types of lines in the table, GFA may contain
+other line types starting with different letters. Each line may optionally have
+additional SAM-like typed key-value pairs.}
+\end{table}
+
+GFA is a concise assembly format (Table~\ref{tab:gfa}; http://bit.ly/gfaspec) initially proposed by
+us prior to miniasm and later improved by community (P. Melsted, S. Jackman,
+J. Simpson and E. Garrison, personal communication). GFA has an explicit
+relationship to an assembly graph -- an `S' line in the GFA corresponds to a
+vertex and its complement in the graph; an `L' line corresponds to an edge and
+its complement. GFA is able to represent graphs produced at all the stages of
+an assembly pipeline, from initial read overlaps to the unitig relationship in
+the final assembly.
+
+FASTG (http://bit.ly/fastgfmt) is another assembly format prior to GFA.
+It uses different terminologies. A vertex in an assembly graph is called an
+edge in FASTG, and an edge is called an adjacency. In FASTG, subgraphs can be
+nested, though no tools work with nested graphs due to technical complications.
+In addition, with nesting, one assembly graph can be represented in distinct
+ways, which we regard as a limitation of FASTG.
+
+\subsection{Evaluating the layout accuracy}\label{sec:eval}
+
+Miniasm outputs the approximate positions of trimmed reads on the resulting
+unitigs. We extract these reads, map to the true assembly with minimap (option:
+`-L100 -m0 -w5') and select the best mapping for each read. For a read $i$, let
+${\rm utg}_i$ be the unitig name and ${\rm rank}_i$ be its index on ${\rm
+utg}_i$ (i.e. read $i$ is the ${\rm rank}_i$-th read on the unitig). If two
+reads $i$ and $j$ are mapped adjacently on the true assembly, we say the
+adjacency is \emph{$w$-consistent}, if (i) ${\rm utg}_i={\rm utg}_j$ and $|{\rm
+rank}_i-{\rm rank}_j|<w$, or (ii) both read $i$ and $j$ are the first or the
+last $w$ reads of some unitigs. We use $w=5$ to detect large structural
+misassemblies.
+
+\end{methods}
+
+\begin{table}[tb]
+\processtable{Evaluation data sets}
+{\footnotesize\label{tab:data}
+\begin{tabular}{llrrr}
+\toprule
+Name & Species & Size & Cov. & N50 \\
+\midrule
+PB-ce-40X & {\it Caenorhabditis elegans} & 104M & 45 & 16572 \\
+ERS473430 & {\it Citrobacter koseri} & 4.9M & 106 & 7543 \\
+ERS544009 & {\it Yersinia pseudotuberculosis} & 4.7M & 147 & 9002 \\
+ERS554120 & {\it Pseudomonas aeruginosa} & 6.4M & 90 & 7106 \\
+ERS605484 & {\it Vibrio vulnificus} & 5.0M & 155 & 5091 \\
+ERS617393 & {\it Acinetobacter baumannii} & 4.0M & 237 & 7911 \\
+ERS646601 & {\it Haemophilus influenzae} & 1.9M & 258 & 4081 \\
+ERS659581 & {\it Klebsiella sp.} & 5.1M & 129 & 8031 \\
+ERS670327 & {\it Shimwellia blattae} & 4.2M & 155 & 6765 \\
+ERS685285 & {\it Streptococcus sanguinis} & 2.4M & 224 & 5791 \\
+ERS743109 & {\it Salmonella enterica} & 4.8M & 188 & 6051 \\
+PB-ecoli & {\it Escherichia coli} & 4.6M & 160 & 13976 \\
+PBcR-PB-ec & {\it Escherichia coli} & 4.6M & 30 & 11757 \\
+PBcR-ONT-ec & {\it Escherichia coli} & 4.6M & 29 & 9356 \\
+MAP-006-1 & {\it Escherichia coli} & 4.6M & 54 & 10892 \\
+MAP-006-2 & {\it Escherichia coli} & 4.6M & 30 & 10794 \\
+MAP-006-pcr-1 & {\it Escherichia coli} & 4.6M & 30 & 8080 \\
+MAP-006-pcr-2 & {\it Escherichia coli} & 4.6M & 60 & 8064 \\
+\botrule
+\end{tabular}
+}{Evaluation data set name, species, reference genome size, theoretical
+sequencing coverage and the N50 read length. Names starting with ``MAP'' are
+unpublished recent ONT data provided by the Loman lab (http://bit.ly/loman006).
+Names starting with ``ERS'' are accession numbers of unpublished PacBio data
+from the NCTC project (http://bit.ly/nctc3k). PB-ecoli and PB-ce-40X are PacBio
+public data sets sequenced with the P6/C4 chemistry (http://bit.ly/pbpubdat;
+retrieved on 11/03/2015). PBcR-PB-ec is the PacBio sample data (P5/C3
+chemistry) used in the tutorial of the PBcR pipeline; PBcR-ONT-ec is the ONT
+example originally used by \citet{Loman:2015xu}. `pls2fasta --trimByRegion' was
+applied to ERS* and PB-ecoli data sets as they do not provide read sequences in
+the FASTQ format.}
+\end{table}
+
+\section{Results}
+
+\subsection{The accuracy of minimap}
+
+We mapped a human PacBio run ``m130928\_232712\_42213\_*.1.*''
+(http://bit.ly/chm1p5c3) with minimap and BWA-MEM~\citep{Li:2013aa}
+against GRCh37 plus decoy sequences (http://bit.ly/GRCh37d5).
+We started from 23,235 reads (131Mbp), filtered out 7,593 reads (10Mbp) without
+$\ge$2kbp BWA-MEM alignments, and further dropped 815 reads (11Mbp) with two or more
+$\ge$2kbp chimeric alignments and 598 reads (4Mbp) with mapping quality below 10.
+Of the remaining reads, we found only 2.0\% not overlapping the best minimap
+mapping of the same read. The majority of them hit to the decoy sequence where
+defining the true alignment is challenging as decoy is enriched with incomplete
+segments of centromeric repeats. If we exclude hits to the decoy, the
+percentage drops to 0.7\%. On this input, minimap is 50 times faster than
+BWA-MEM, while finding similar best mapping positions. This experiment
+evaluates both the sensitivity and the specificity of minimap: if minimap had
+low sensitivity, it would miss the BWA-MEM mapping completely; if minimap had
+low specificity, its best mapping would often be a wrong mapping.
+
+To test the sensitivity for read overlapping, we aligned all reads from
+PBcR-PB-ec (Table~\ref{tab:data}) against the reference genome with BWA-MEM,
+extracted reads with mapping quality $\ge$10, and identified $\ge$2kb overlaps
+between the extracted reads based on their positions on the reference genome.
+Minimap finds 93\% of these overlaps. It is more sensitive than MHAP in its
+sensitive mode (78\%) but less than DALIGNER (98\%).
+
+\subsection{Assembling bacterial genomes}
+
+We evaluated the performance of miniasm on 17 bacterial data sets
+(Table~\ref{tab:data}) with command line `minimap -Sw5 -L100 -m0 reads.fa reads.fa $|$
+miniasm -f reads.fa -'. Miniasm is able to derive a single contig per
+chromosome/plasmid for all but four data sets: 3 extra $>$50kb contigs for
+ERS554120, and 1 extra contig for ERS605484, PBcR-ONT-ec and MAP-006-pcr-1
+each. In the dotter plot between the assembly and the reference genome (similar
+to Figure~\ref{fig:ce}), no large-scale misassemblies are observed. We also
+applied the method in Section~\ref{sec:eval}. Except ERS473430, the miniasm layouts are
+5-consistent with the reference assemblies. For ERS473430, the NCTC project page
+claimed the sample has a plasmid. Miniasm gives two contigs, but the NCTC
+assembly has one contig only. The difference in layout may be an error in the
+NCTC assembly.
+
+%Encouraged by the single-contig assembly for PBcR-PB-ec at only 30-fold
+%coverage, we randomly down-sampled PacBio data sets and tried to assemble the
+%subset. For PB-ecoli, miniasm still produced a single contig at 24-fold
+%coverage, or two contigs at 20-fold. For the other data sets, however, miniasm
+%generated fragmented assemblies when we sampled a third of reads. We speculate
+%the shorter read lengths of the ERS* data sets made it more difficult to
+%produce good assemblies at relatively low coverage.
+
+We have also run the PBcR pipeline~\citep{Berlin:2015xy}. PBcR requires a spec
+file. We took `pacbio.spec' from the PBcR-PB-ec example and `oxford.spec' from
+PBcR-ONT-ec, and applied them to all data sets based on their data types. MAP*
+data sets only provide FASTA sequences for download. We assigned quality 9 to
+all bases as PBcR requires base quality. PBcR assembled all PacBio data sets
+without extra contigs longer than 50kb -- better than miniasm. However, on the
+ONT data sets, PBcR produced more fragmented assemblies for MAP-006-2,
+MAP-006-pcr-1 and MAP-006-pcr-2; the PBcR-ONT-ec assembly is 300kb shorter.
+
+With four CPU cores, it took miniasm 14 seconds to assemble the 30-fold
+PBcR-PB-ec data set and 2 minutes to assemble the 160-fold PB-ecoli data set.
+PBcR, with four CPU cores, too, is about 700 times slower on PBcR-PB-ecoli and
+60 times slower on PB-ecoli. It is slower on low-coverage data
+because PBcR automatically switches to the slower sensitive mode. Here we
+should remind readers that without an error correction stage, the contig
+sequences generated by miniasm are of much lower accuracy in comparison to
+PBcR. Nonetheless, miniasm is still tens of times faster than PBcR excluding
+the time spent on error correction.
+
+\subsection{Assembling a C. elegans genome}
+
+\begin{figure}[tb]
+\includegraphics[width=.48\textwidth]{ce}
+\caption{Dotter plot comparing the miniasm assembly and the {\it C. elegans}
+reference genome. Thin gray lines mark the contig or chromosome boundaries. The
+three arrows indicate large-scale misassemblies visible from the
+plot. The mapping is done with `minimap -L500'.}\label{fig:ce}
+\end{figure}
+
+We assembled a 45-fold {\it C. elegans} data set (Table~\ref{tab:data}). With 16 CPU cores,
+miniasm assembled the data in 9 minutes, achieving an N50 size 2.8Mb. From the
+dotter plot (Figure~\ref{fig:ce}), we observed three structural misassemblies
+(readers are advised to zoom into the vector graph to see the details).
+PacBio has assembled the same data set with HGAP3~\citep{Chin:2013qr}. HGAP3
+produces shorter contigs (N50=1.6Mb), but does not incur large-scale
+misassemblies visible from the dotter plot between the {\it C. elegans}
+reference genome and the contigs.
+
+When we take the {\it C. elegans} reference genome as the truth, the method in
+Section~\ref{sec:eval} also identifies the three structural misassemblies. The
+method additionally finds eight intra-unitig and one inter-unitig
+inconsistencies. In all cases, miniasm agrees with HGAP3, suggesting these
+inconsistencies may be true structural variations between the reference strain
+and the sequenced strain.
+
+We have also tried PBcR on this data set. Based on the intermediate progress
+report, we estimated that with 16 CPU cores, it would take a week or so to
+finish the assembly in the automatically chosen `sensitive' mode.
+
+For this data set, minimap takes 27GB RAM at the peak. As minimap loads 4Gbp
+bases to index, the peak RAM will be capped around 27GB. The memory used by
+miniasm is proportional to the number of overlaps. Although it only takes
+1.3GB RAM here, it will become the limiting factor for larger data sets.
+
+\subsection{Switching read overlappers}
+
+Miniasm also works with other overlappers when we convert their output format
+to PAF. On the 30-fold PBcR-PB-ec data set, we are able to produce a single
+contig with DALIGNER (option -k15 -h50), MHAP (option
+\mbox{--pacbio-sensitive}) and GraphMap (option -w owler). DALIGNER is the
+fastest, taking 65 seconds with four CPUs. Minimap is five times as fast on
+this data set and is 18 times as fast on PB-ecoli at 160-fold. Minimap is
+faster on larger data sets possibly because without staging all possible hits
+in RAM, minimap is able to process more reads in a batch while a large batch
+usually helps performance. We should note that DALIGNER generates alignments
+while minimap does not. Minimap would probably have a similar performance if it
+included an alignment step.
+
+\section{Discussions}
+
+Miniasm implements the `O' and `L' steps in the Overlap-Layout-Consensus (OLC)
+assembly paradigm. It confirms long noisy reads can be assembled without an
+error correction stage, and without this stage, the assembly process can be
+greatly accelerated and simplified, while achieving comparable contiguity and
+large-scale accuracy to existing pipelines, at least for genomes without
+excessive repetitive sequences. Although without the `C' step, miniasm
+cannot produce high-quality consensus for many analyses, it opens the door
+to ultrafast assembly if we can develop a fast consensus tool matching the
+speed of minimap and miniasm. In addition, MinION has a `read-until' mode,
+allowing users to pause sequencing and reload samples. Fast layout by miniasm
+could already help to decide if enough data have been collected.
+
+Our main concern with miniasm is that when we look at a low-identity match
+between two noisy reads, it is difficult to tell whether the low identity is
+caused by the stochastically higher base error rate on reads, or because
+reads come from two recent segmental duplications.
+In comparison, error correction takes the advantage of multiple reads and in
+theory has more power to distinguish high error rate from duplications/repeats.
+Bacteria and {\it C. elegans} evaluated in this article are repeat sparse.
+We are yet to know the performance of miniasm given repeat-rich genomes. In addition, miniasm has
+not been optimized for large repeat-rich genomes. It reads all hits into RAM,
+which may not be practical when there are too many. We need to filter
+repetitive hits, introduce disk-based algorithms (e.g. for sorting) or stream
+hits before removing contained reads. Working with large complex genomes will
+be an important future direction.
+
+%Minimap is primarily used as a read overlapper in this article. It in fact has a
+%wider range of applications in addition to overlapping. For example, with four
+%CPU cores, it is able to map 1.6Gb PacBio reads to the human genome in 2.5
+%minutes, map 1Gb {\it E. coli} reads to pre-indexed 9.6Gb bacterial genome in 3
+%minutes and to pre-indexed 100Gb nt database in an hour with a third of time
+%spent on loading the index from the network file system. It can also map 2800
+%bacterial genomes to themselves in an hour. Minimap is fast, but is not as
+%sensitive as proper whole-genome aligners and recent long-read aligners such as
+%LASTZ~\citep{harris:2007aa}, LAST~\citep{Kiebasa:2011aa} and GraphMap. They use
+%shorter spaced seeds which greatly help sensitivity at the cost of performance.
+
+Oxford Nanopore is working on PromethION and PacBio will ship PacBio Sequel
+later this year. Both sequencers promise significantly reduced sequencing cost and
+increased throughput, which may stimulate the adoption of long-read sequencing
+and subsequently the development of long-read mappers and assemblers. We hope
+in this process, the community could standardize the input and output formats
+of various tools, so that a developer could focus on a component he or she
+understands best. Such a modular approach has been proved to be fruitful in the
+development of short-read tools -- in fact, the best short-read pipelines all
+consist of components developed by different groups -- and will be equally
+beneficial to the future development of long-read mappers and assemblers.
+
+\section*{Acknowledgement}
+
+We thank P\'all Melsted for maintaining the GFA spec and are grateful to Gene
+Myers, Jason Chin, Adam Phillippy, Jared Simpson, Zamin Iqbal, Nick Loman and
+Ivan Sovic for their presentations, talks, comments on social media and
+unpublished works which have greatly influenced and helped the development of
+minimap and miniasm.
+
+\paragraph{Funding\textcolon} NHGRI U54HG003037; NIH GM100233
+
+\bibliography{miniasm}
+\end{document}
diff --git a/tex/natbib.bst b/tex/natbib.bst
new file mode 100644
index 0000000..a679e1d
--- /dev/null
+++ b/tex/natbib.bst
@@ -0,0 +1,1288 @@
+%%
+%% This is file `natbib.bst', generated
+%% on <1994/9/16> with the docstrip utility (2.2h).
+%%
+%% The original source files were:
+%%
+%% genbst.mbs (with options: `ay,nat,seq-lab,nm-rev,dt-beg,yr-par,vol-bf,
+%% volp-com,etal-it')
+%% ----------------------------------------
+%% *** Personal bib style, PWD ***
+%%
+%% (Here are the specifications of the source file)
+%% \ProvidesFile{genbst.mbs}[1994/09/16 1.5 (PWD)]
+%% For use with BibTeX version 0.99a or later
+%% and with LaTeX 2.09 or 2e
+%%-------------------------------------------------------------------
+%% NOTICE:
+%% This file may be used for non-profit purposes.
+%% It may not be distributed in exchange for money,
+%% other than distribution costs.
+%%
+%% The author provides it `as is' and does not guarantee it in any way.
+%%
+%% Copyright (C) 1994 Patrick W. Daly
+%% Max-Planck-Institut f\"ur Aeronomie
+%% Postfach 20
+%% D-37189 Katlenburg-Lindau
+%% Germany
+%%
+%% E-mail:
+%% SPAN-- nsp::linmpi::daly (note nsp also known as ecd1)
+%% Internet-- daly@linmpi.dnet.gwdg.de
+%%-----------------------------------------------------------
+%% \CharacterTable
+%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
+%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
+%% Digits \0\1\2\3\4\5\6\7\8\9
+%% Exclamation \! Double quote \" Hash (number) \#
+%% Dollar \$ Percent \% Ampersand \&
+%% Acute accent \' Left paren \( Right paren \)
+%% Asterisk \* Plus \+ Comma \,
+%% Minus \- Point \. Solidus \/
+%% Colon \: Semicolon \; Less than \<
+%% Equals \= Greater than \> Question mark \?
+%% Commercial at \@ Left bracket \[ Backslash \\
+%% Right bracket \] Circumflex \^ Underscore \_
+%% Grave accent \` Left brace \{ Vertical bar \|
+%% Right brace \} Tilde \~}
+%%---------------------------------------------------------------------
+ % This is an author-year citation style bibliography. As such, it is
+ % non-standard LaTeX, and requires a special package file to function properly.
+ % Such a package is natbib.sty by Patrick W. Daly
+ % The form of the \bibitem entries is
+ % \bibitem[Jones et al.(1990)]{key}...
+ % \bibitem[Jones et al.(1990)Jones, Baker, and Smith]{key}...
+ % The essential feature is that the label (the part in brackets) consists
+ % of the author names, as they should appear in the citation, with the year
+ % in parentheses following. There must be no space before the opening
+ % parenthesis!
+ % With natbib v5.3, a full list of authors may also follow the year.
+ % In natbib.sty, it is possible to define the type of enclosures that is
+ % really wanted (brackets or parentheses), but in either case, there must
+ % be parentheses in the label.
+ % The \cite command functions as follows:
+ % \cite{key} ==>> Jones et al. (1990)
+ % \cite[]{key} ==>> (Jones et al., 1990)
+ % \cite[chap. 2]{key} ==>> (Jones et al., 1990, chap. 2)
+ % \cite[e.g.][]{key} ==>> (e.g. Jones et al., 1990)
+ % \cite[e.g.][p. 32]{key} ==>> (e.g. Jones et al., p. 32)
+ % \citeauthor{key} Jones et al.
+ % \citefullauthor{key} Jones, Baker, and Smith
+ % \citeyear{key} 1990
+%%---------------------------------------------------------------------
+
+ENTRY
+ { address
+ author
+ booktitle
+ chapter
+ edition
+ editor
+ howpublished
+ institution
+ journal
+ key
+ month
+ note
+ number
+ organization
+ pages
+ publisher
+ school
+ series
+ title
+ type
+ volume
+ year
+ }
+ {}
+ { label extra.label sort.label }
+
+INTEGERS { output.state before.all mid.sentence after.sentence after.block }
+
+FUNCTION {init.state.consts}
+{ #0 'before.all :=
+ #1 'mid.sentence :=
+ #2 'after.sentence :=
+ #3 'after.block :=
+}
+
+STRINGS { s t }
+
+FUNCTION {output.nonnull}
+{ 's :=
+ output.state mid.sentence =
+ { ", " * write$ }
+ { output.state after.block =
+ { add.period$ write$
+ newline$
+ "\newblock " write$
+ }
+ { output.state before.all =
+ 'write$
+ { add.period$ " " * write$ }
+ if$
+ }
+ if$
+ mid.sentence 'output.state :=
+ }
+ if$
+ s
+}
+
+FUNCTION {output}
+{ duplicate$ empty$
+ 'pop$
+ 'output.nonnull
+ if$
+}
+
+FUNCTION {output.check}
+{ 't :=
+ duplicate$ empty$
+ { pop$ "empty " t * " in " * cite$ * warning$ }
+ 'output.nonnull
+ if$
+}
+
+FUNCTION {fin.entry}
+{ add.period$
+ write$
+ newline$
+}
+
+FUNCTION {new.block}
+{ output.state before.all =
+ 'skip$
+ { after.block 'output.state := }
+ if$
+}
+
+FUNCTION {new.sentence}
+{ output.state after.block =
+ 'skip$
+ { output.state before.all =
+ 'skip$
+ { after.sentence 'output.state := }
+ if$
+ }
+ if$
+}
+
+FUNCTION {not}
+{ { #0 }
+ { #1 }
+ if$
+}
+
+FUNCTION {and}
+{ 'skip$
+ { pop$ #0 }
+ if$
+}
+
+FUNCTION {or}
+{ { pop$ #1 }
+ 'skip$
+ if$
+}
+
+FUNCTION {non.stop}
+{ duplicate$
+ "}" * add.period$
+ #-1 #1 substring$ "." =
+}
+
+FUNCTION {new.block.checkb}
+{ empty$
+ swap$ empty$
+ and
+ 'skip$
+ 'new.block
+ if$
+}
+
+FUNCTION {field.or.null}
+{ duplicate$ empty$
+ { pop$ "" }
+ 'skip$
+ if$
+}
+
+FUNCTION {emphasize}
+{ duplicate$ empty$
+ { pop$ "" }
+ { "{\em " swap$ * non.stop
+ { "\/}" * }
+ { "}" * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {bolden}
+{ duplicate$ empty$
+ { pop$ "" }
+ { "{\bf " swap$ * "}" * }
+ if$
+}
+
+INTEGERS { nameptr namesleft numnames }
+
+FUNCTION {format.names}
+{ 's :=
+ #1 'nameptr :=
+ s num.names$ 'numnames :=
+ numnames 'namesleft :=
+ { namesleft #0 > }
+ { s nameptr
+ "{vv~}{ll}{, jj}{, f.}" format.name$ 't :=
+ nameptr #1 >
+ {
+ namesleft #1 >
+ { ", " * t * }
+ {
+ numnames #2 >
+ { "," * }
+ 'skip$
+ if$
+ t "others" =
+ { " " * "et~al." emphasize * }
+ { " and " * t * }
+ if$
+ }
+ if$
+ }
+ 't
+ if$
+ nameptr #1 + 'nameptr :=
+ namesleft #1 - 'namesleft :=
+ }
+ while$
+}
+
+FUNCTION {format.names.ed}
+{ 's :=
+ #1 'nameptr :=
+ s num.names$ 'numnames :=
+ numnames 'namesleft :=
+ { namesleft #0 > }
+ { s nameptr
+ "{f.~}{vv~}{ll}{, jj}"
+ format.name$ 't :=
+ nameptr #1 >
+ {
+ namesleft #1 >
+ { ", " * t * }
+ {
+ numnames #2 >
+ { "," * }
+ 'skip$
+ if$
+ t "others" =
+ { " " * "et~al." emphasize * }
+ { " and " * t * }
+ if$
+ }
+ if$
+ }
+ 't
+ if$
+ nameptr #1 + 'nameptr :=
+ namesleft #1 - 'namesleft :=
+ }
+ while$
+}
+
+FUNCTION {format.key}
+{ empty$
+ { key field.or.null }
+ { "" }
+ if$
+}
+
+FUNCTION {format.authors}
+{ author empty$
+ { "" }
+ { author format.names }
+ if$
+}
+
+FUNCTION {format.editors}
+{ editor empty$
+ { "" }
+ { editor format.names
+ editor num.names$ #1 >
+ { ", editors" * }
+ { ", editor" * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.in.editors}
+{ editor empty$
+ { "" }
+ { editor format.names.ed
+ editor num.names$ #1 >
+ { ", editors" * }
+ { ", editor" * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.title}
+{ title empty$
+ { "" }
+ { title "t" change.case$
+ }
+ if$
+}
+
+FUNCTION {format.full.names}
+{'s :=
+ #1 'nameptr :=
+ s num.names$ 'numnames :=
+ numnames 'namesleft :=
+ { namesleft #0 > }
+ { s nameptr
+ "{vv~}{ll}" format.name$ 't :=
+ nameptr #1 >
+ {
+ namesleft #1 >
+ { ", " * t * }
+ {
+ numnames #2 >
+ { "," * }
+ 'skip$
+ if$
+ t "others" =
+ { " " * "et~al." emphasize * }
+ { " and " * t * }
+ if$
+ }
+ if$
+ }
+ 't
+ if$
+ nameptr #1 + 'nameptr :=
+ namesleft #1 - 'namesleft :=
+ }
+ while$
+}
+
+FUNCTION {author.editor.key.full}
+{ author empty$
+ { editor empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { editor format.full.names }
+ if$
+ }
+ { author format.full.names }
+ if$
+}
+
+FUNCTION {author.key.full}
+{ author empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { author format.full.names }
+ if$
+}
+
+FUNCTION {editor.key.full}
+{ editor empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { editor format.full.names }
+ if$
+}
+
+FUNCTION {make.full.names}
+{ type$ "book" =
+ type$ "inbook" =
+ or
+ 'author.editor.key.full
+ { type$ "proceedings" =
+ 'editor.key.full
+ 'author.key.full
+ if$
+ }
+ if$
+}
+
+FUNCTION {output.bibitem}
+{ newline$
+ "\bibitem[" write$
+ label write$
+ ")" make.full.names * "]{" * write$
+ cite$ write$
+ "}" write$
+ newline$
+ ""
+ before.all 'output.state :=
+}
+
+FUNCTION {n.dashify}
+{ 't :=
+ ""
+ { t empty$ not }
+ { t #1 #1 substring$ "-" =
+ { t #1 #2 substring$ "--" = not
+ { "--" *
+ t #2 global.max$ substring$ 't :=
+ }
+ { { t #1 #1 substring$ "-" = }
+ { "-" *
+ t #2 global.max$ substring$ 't :=
+ }
+ while$
+ }
+ if$
+ }
+ { t #1 #1 substring$ *
+ t #2 global.max$ substring$ 't :=
+ }
+ if$
+ }
+ while$
+}
+
+FUNCTION {word.in}
+{ "In " }
+
+FUNCTION {format.date}
+{ year duplicate$ empty$
+ { "empty year in " cite$ * "; set to ????" * warning$
+ pop$ "????" }
+ 'skip$
+ if$
+ before.all 'output.state :=
+ " (" swap$ * extra.label * ")" *
+}
+
+FUNCTION {format.btitle}
+{ title emphasize
+}
+
+FUNCTION {tie.or.space.connect}
+{ duplicate$ text.length$ #3 <
+ { "~" }
+ { " " }
+ if$
+ swap$ * *
+}
+
+FUNCTION {either.or.check}
+{ empty$
+ 'pop$
+ { "can't use both " swap$ * " fields in " * cite$ * warning$ }
+ if$
+}
+
+FUNCTION {format.bvolume}
+{ volume empty$
+ { "" }
+ { "volume" volume tie.or.space.connect
+ series empty$
+ 'skip$
+ { " of " * series emphasize * }
+ if$
+ "volume and number" number either.or.check
+ }
+ if$
+}
+
+FUNCTION {format.number.series}
+{ volume empty$
+ { number empty$
+ { series field.or.null }
+ { output.state mid.sentence =
+ { "number" }
+ { "Number" }
+ if$
+ number tie.or.space.connect
+ series empty$
+ { "there's a number but no series in " cite$ * warning$ }
+ { " in " * series * }
+ if$
+ }
+ if$
+ }
+ { "" }
+ if$
+}
+
+FUNCTION {format.edition}
+{ edition empty$
+ { "" }
+ { output.state mid.sentence =
+ { edition "l" change.case$ " edition" * }
+ { edition "t" change.case$ " edition" * }
+ if$
+ }
+ if$
+}
+
+INTEGERS { multiresult }
+
+FUNCTION {multi.page.check}
+{ 't :=
+ #0 'multiresult :=
+ { multiresult not
+ t empty$ not
+ and
+ }
+ { t #1 #1 substring$
+ duplicate$ "-" =
+ swap$ duplicate$ "," =
+ swap$ "+" =
+ or or
+ { #1 'multiresult := }
+ { t #2 global.max$ substring$ 't := }
+ if$
+ }
+ while$
+ multiresult
+}
+
+FUNCTION {format.pages}
+{ pages empty$
+ { "" }
+ { pages multi.page.check
+ { "pages" pages n.dashify tie.or.space.connect }
+ { "page" pages tie.or.space.connect }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.vol.num.pages}
+{ volume field.or.null
+ bolden
+ number empty$
+ 'skip$
+ { "(" number * ")" * *
+ volume empty$
+ { "there's a number but no volume in " cite$ * warning$ }
+ 'skip$
+ if$
+ }
+ if$
+ pages empty$
+ 'skip$
+ { duplicate$ empty$
+ { pop$ format.pages }
+ { ", " * pages n.dashify * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.chapter.pages}
+{ chapter empty$
+ 'format.pages
+ { type empty$
+ { "chapter" }
+ { type "l" change.case$ }
+ if$
+ chapter tie.or.space.connect
+ pages empty$
+ 'skip$
+ { ", " * format.pages * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.in.ed.booktitle}
+{ booktitle empty$
+ { "" }
+ { editor empty$
+ { word.in booktitle emphasize * }
+ { word.in format.in.editors * ", " * booktitle emphasize * }
+ if$
+ }
+ if$
+}
+
+FUNCTION {format.thesis.type}
+{ type empty$
+ 'skip$
+ { pop$
+ type "t" change.case$
+ }
+ if$
+}
+
+FUNCTION {format.tr.number}
+{ type empty$
+ { "Technical Report" }
+ 'type
+ if$
+ number empty$
+ { "t" change.case$ }
+ { number tie.or.space.connect }
+ if$
+}
+
+FUNCTION {format.article.crossref}
+{
+ word.in
+ "\cite{" * crossref * "}" *
+}
+
+FUNCTION {format.book.crossref}
+{ volume empty$
+ { "empty volume in " cite$ * "'s crossref of " * crossref * warning$
+ word.in
+ }
+ { "Volume" volume tie.or.space.connect
+ " of " *
+ }
+ if$
+ "\cite{" * crossref * "}" *
+}
+
+FUNCTION {format.incoll.inproc.crossref}
+{
+ word.in
+ "\cite{" * crossref * "}" *
+}
+
+FUNCTION {article}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ crossref missing$
+ { journal emphasize "journal" output.check
+ format.vol.num.pages output
+ }
+ { format.article.crossref output.nonnull
+ format.pages output
+ }
+ if$
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {book}
+{ output.bibitem
+ author empty$
+ { format.editors "author and editor" output.check
+ editor format.key output
+ }
+ { format.authors output.nonnull
+ crossref missing$
+ { "author and editor" editor either.or.check }
+ 'skip$
+ if$
+ }
+ if$
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ crossref missing$
+ { format.bvolume output
+ new.block
+ format.number.series output
+ new.sentence
+ publisher "publisher" output.check
+ address output
+ }
+ {
+ new.block
+ format.book.crossref output.nonnull
+ }
+ if$
+ format.edition output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {booklet}
+{ output.bibitem
+ format.authors output
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ howpublished output
+ address output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {inbook}
+{ output.bibitem
+ author empty$
+ { format.editors "author and editor" output.check
+ editor format.key output
+ }
+ { format.authors output.nonnull
+ crossref missing$
+ { "author and editor" editor either.or.check }
+ 'skip$
+ if$
+ }
+ if$
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ crossref missing$
+ { format.bvolume output
+ format.chapter.pages "chapter and pages" output.check
+ new.block
+ format.number.series output
+ new.sentence
+ publisher "publisher" output.check
+ address output
+ }
+ { format.chapter.pages "chapter and pages" output.check
+ new.block
+ format.book.crossref output.nonnull
+ }
+ if$
+ format.edition output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {incollection}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ crossref missing$
+ { format.in.ed.booktitle "booktitle" output.check
+ format.bvolume output
+ format.number.series output
+ format.chapter.pages output
+ new.sentence
+ publisher "publisher" output.check
+ address output
+ format.edition output
+ }
+ { format.incoll.inproc.crossref output.nonnull
+ format.chapter.pages output
+ }
+ if$
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {inproceedings}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ crossref missing$
+ { format.in.ed.booktitle "booktitle" output.check
+ format.bvolume output
+ format.number.series output
+ format.pages output
+ address output
+ new.sentence
+ organization output
+ publisher output
+ }
+ { format.incoll.inproc.crossref output.nonnull
+ format.pages output
+ }
+ if$
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {conference} { inproceedings }
+
+FUNCTION {manual}
+{ output.bibitem
+ format.authors output
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ organization address new.block.checkb
+ organization output
+ address output
+ format.edition output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {mastersthesis}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ new.block
+ "Master's thesis" format.thesis.type output.nonnull
+ school "school" output.check
+ address output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {misc}
+{ output.bibitem
+ format.authors output
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title output
+ new.block
+ howpublished output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {phdthesis}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ new.block
+ "Ph.D. thesis" format.thesis.type output.nonnull
+ school "school" output.check
+ address output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {proceedings}
+{ output.bibitem
+ format.editors output
+ editor format.key output
+ format.date "year" output.check
+ new.block
+ format.btitle "title" output.check
+ format.bvolume output
+ format.number.series output
+ address output
+ new.sentence
+ organization output
+ publisher output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {techreport}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ format.tr.number output.nonnull
+ institution "institution" output.check
+ address output
+ new.block
+ note output
+ fin.entry
+}
+
+FUNCTION {unpublished}
+{ output.bibitem
+ format.authors "author" output.check
+ author format.key output
+ format.date "year" output.check
+ new.block
+ format.title "title" output.check
+ new.block
+ note "note" output.check
+ fin.entry
+}
+
+FUNCTION {default.type} { misc }
+
+MACRO {jan} {"January"}
+
+MACRO {feb} {"February"}
+
+MACRO {mar} {"March"}
+
+MACRO {apr} {"April"}
+
+MACRO {may} {"May"}
+
+MACRO {jun} {"June"}
+
+MACRO {jul} {"July"}
+
+MACRO {aug} {"August"}
+
+MACRO {sep} {"September"}
+
+MACRO {oct} {"October"}
+
+MACRO {nov} {"November"}
+
+MACRO {dec} {"December"}
+
+MACRO {acmcs} {"ACM Computing Surveys"}
+
+MACRO {acta} {"Acta Informatica"}
+
+MACRO {cacm} {"Communications of the ACM"}
+
+MACRO {ibmjrd} {"IBM Journal of Research and Development"}
+
+MACRO {ibmsj} {"IBM Systems Journal"}
+
+MACRO {ieeese} {"IEEE Transactions on Software Engineering"}
+
+MACRO {ieeetc} {"IEEE Transactions on Computers"}
+
+MACRO {ieeetcad}
+ {"IEEE Transactions on Computer-Aided Design of Integrated Circuits"}
+
+MACRO {ipl} {"Information Processing Letters"}
+
+MACRO {jacm} {"Journal of the ACM"}
+
+MACRO {jcss} {"Journal of Computer and System Sciences"}
+
+MACRO {scp} {"Science of Computer Programming"}
+
+MACRO {sicomp} {"SIAM Journal on Computing"}
+
+MACRO {tocs} {"ACM Transactions on Computer Systems"}
+
+MACRO {tods} {"ACM Transactions on Database Systems"}
+
+MACRO {tog} {"ACM Transactions on Graphics"}
+
+MACRO {toms} {"ACM Transactions on Mathematical Software"}
+
+MACRO {toois} {"ACM Transactions on Office Information Systems"}
+
+MACRO {toplas} {"ACM Transactions on Programming Languages and Systems"}
+
+MACRO {tcs} {"Theoretical Computer Science"}
+
+READ
+
+FUNCTION {sortify}
+{ purify$
+ "l" change.case$
+}
+
+INTEGERS { len }
+
+FUNCTION {chop.word}
+{ 's :=
+ 'len :=
+ s #1 len substring$ =
+ { s len #1 + global.max$ substring$ }
+ 's
+ if$
+}
+
+FUNCTION {format.lab.names}
+{ 's :=
+ s #1 "{vv~}{ll}" format.name$
+ s num.names$ duplicate$
+ #2 >
+ { pop$ " " * "et~al." emphasize * }
+ { #2 <
+ 'skip$
+ { s #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" =
+ { " " * "et~al." emphasize * }
+ { " and " * s #2 "{vv~}{ll}" format.name$ * }
+ if$
+ }
+ if$
+ }
+ if$
+}
+
+FUNCTION {author.key.label}
+{ author empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { author format.lab.names }
+ if$
+}
+
+FUNCTION {author.editor.key.label}
+{ author empty$
+ { editor empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { editor format.lab.names }
+ if$
+ }
+ { author format.lab.names }
+ if$
+}
+
+FUNCTION {editor.key.label}
+{ editor empty$
+ { key empty$
+ { cite$ #1 #3 substring$ }
+ 'key
+ if$
+ }
+ { editor format.lab.names }
+ if$
+}
+
+FUNCTION {calc.label}
+{ type$ "book" =
+ type$ "inbook" =
+ or
+ 'author.editor.key.label
+ { type$ "proceedings" =
+ 'editor.key.label
+ 'author.key.label
+ if$
+ }
+ if$
+ "("
+ *
+ year duplicate$ empty$
+ { pop$ "????" }
+ { purify$ #-1 #4 substring$ }
+ if$
+ *
+ 'label :=
+}
+
+FUNCTION {sort.format.names}
+{ 's :=
+ #1 'nameptr :=
+ ""
+ s num.names$ 'numnames :=
+ numnames 'namesleft :=
+ { namesleft #0 > }
+ { nameptr #1 >
+ { " " * }
+ 'skip$
+ if$
+ s nameptr
+ "{vv{ } }{ll{ }}{ f{ }}{ jj{ }}"
+ format.name$ 't :=
+ nameptr numnames = t "others" = and
+ { "et al" * }
+ { numnames #2 > nameptr #2 = and
+ { "zzzzzz" * #1 'namesleft := }
+ { t sortify * }
+ if$
+ }
+ if$
+ nameptr #1 + 'nameptr :=
+ namesleft #1 - 'namesleft :=
+ }
+ while$
+}
+
+FUNCTION {sort.format.title}
+{ 't :=
+ "A " #2
+ "An " #3
+ "The " #4 t chop.word
+ chop.word
+ chop.word
+ sortify
+ #1 global.max$ substring$
+}
+
+FUNCTION {author.sort}
+{ author empty$
+ { key empty$
+ { "to sort, need author or key in " cite$ * warning$
+ ""
+ }
+ { key sortify }
+ if$
+ }
+ { author sort.format.names }
+ if$
+}
+
+FUNCTION {author.editor.sort}
+{ author empty$
+ { editor empty$
+ { key empty$
+ { "to sort, need author, editor, or key in " cite$ * warning$
+ ""
+ }
+ { key sortify }
+ if$
+ }
+ { editor sort.format.names }
+ if$
+ }
+ { author sort.format.names }
+ if$
+}
+
+FUNCTION {editor.sort}
+{ editor empty$
+ { key empty$
+ { "to sort, need editor or key in " cite$ * warning$
+ ""
+ }
+ { key sortify }
+ if$
+ }
+ { editor sort.format.names }
+ if$
+}
+
+FUNCTION {presort}
+{ calc.label
+ label sortify
+ " "
+ *
+ type$ "book" =
+ type$ "inbook" =
+ or
+ 'author.editor.sort
+ { type$ "proceedings" =
+ 'editor.sort
+ 'author.sort
+ if$
+ }
+ if$
+ #1 entry.max$ substring$
+ 'sort.label :=
+ sort.label
+ *
+ " "
+ *
+ title field.or.null
+ sort.format.title
+ *
+ #1 entry.max$ substring$
+ 'sort.key$ :=
+}
+
+ITERATE {presort}
+
+SORT
+
+STRINGS { last.label next.extra }
+
+INTEGERS { last.extra.num }
+
+FUNCTION {initialize.extra.label.stuff}
+{ #0 int.to.chr$ 'last.label :=
+ "" 'next.extra :=
+ #0 'last.extra.num :=
+}
+
+FUNCTION {forward.pass}
+{ last.label label =
+ { last.extra.num #1 + 'last.extra.num :=
+ last.extra.num int.to.chr$ 'extra.label :=
+ }
+ { "a" chr.to.int$ 'last.extra.num :=
+ "" 'extra.label :=
+ label 'last.label :=
+ }
+ if$
+}
+
+FUNCTION {reverse.pass}
+{ next.extra "b" =
+ { "a" 'extra.label := }
+ 'skip$
+ if$
+ extra.label 'next.extra :=
+ label extra.label * 'label :=
+}
+
+EXECUTE {initialize.extra.label.stuff}
+
+ITERATE {forward.pass}
+
+REVERSE {reverse.pass}
+
+FUNCTION {bib.sort.order}
+{ sort.label
+ " "
+ *
+ year field.or.null sortify
+ *
+ " "
+ *
+ title field.or.null
+ sort.format.title
+ *
+ #1 entry.max$ substring$
+ 'sort.key$ :=
+}
+
+ITERATE {bib.sort.order}
+
+SORT
+
+FUNCTION {begin.bib}
+{ preamble$ empty$
+ 'skip$
+ { preamble$ write$ newline$ }
+ if$
+ "\begin{thebibliography}{}" write$ newline$
+}
+
+EXECUTE {begin.bib}
+
+EXECUTE {init.state.consts}
+
+ITERATE {call.type$}
+
+FUNCTION {end.bib}
+{ newline$
+ "\end{thebibliography}" write$ newline$
+}
+
+EXECUTE {end.bib}
+%% End of customized bst file
+
diff --git a/tex/natbib.sty b/tex/natbib.sty
new file mode 100644
index 0000000..4c8c948
--- /dev/null
+++ b/tex/natbib.sty
@@ -0,0 +1,803 @@
+%%
+%% This is file `natbib.sty',
+%% generated with the docstrip utility.
+%%
+%% The original source files were:
+%%
+%% natbib.dtx (with options: `package,all')
+%% =============================================
+%% IMPORTANT NOTICE:
+%%
+%% This program can be redistributed and/or modified under the terms
+%% of the LaTeX Project Public License Distributed from CTAN
+%% archives in directory macros/latex/base/lppl.txt; either
+%% version 1 of the License, or any later version.
+%%
+%% This is a generated file.
+%% It may not be distributed without the original source file natbib.dtx.
+%%
+%% Full documentation can be obtained by LaTeXing that original file.
+%% Only a few abbreviated comments remain here to describe the usage.
+%% =============================================
+%% Copyright 1993-2000 Patrick W Daly
+%% Max-Planck-Institut f\"ur Aeronomie
+%% Max-Planck-Str. 2
+%% D-37191 Katlenburg-Lindau
+%% Germany
+%% E-mail: daly@linmpi.mpg.de
+\NeedsTeXFormat{LaTeX2e}[1995/06/01]
+\ProvidesPackage{natbib}
+ [2000/07/24 7.0a (PWD)]
+ % This package reimplements the LaTeX \cite command to be used for various
+ % citation styles, both author-year and numerical. It accepts BibTeX
+ % output intended for many other packages, and therefore acts as a
+ % general, all-purpose citation-style interface.
+ %
+ % With standard numerical .bst files, only numerical citations are
+ % possible. With an author-year .bst file, both numerical and
+ % author-year citations are possible.
+ %
+ % If author-year citations are selected, \bibitem must have one of the
+ % following forms:
+ % \bibitem[Jones et al.(1990)]{key}...
+ % \bibitem[Jones et al.(1990)Jones, Baker, and Williams]{key}...
+ % \bibitem[Jones et al., 1990]{key}...
+ % \bibitem[\protect\citeauthoryear{Jones, Baker, and Williams}{Jones
+ % et al.}{1990}]{key}...
+ % \bibitem[\protect\citeauthoryear{Jones et al.}{1990}]{key}...
+ % \bibitem[\protect\astroncite{Jones et al.}{1990}]{key}...
+ % \bibitem[\protect\citename{Jones et al., }1990]{key}...
+ % \harvarditem[Jones et al.]{Jones, Baker, and Williams}{1990}{key}...
+ %
+ % This is either to be made up manually, or to be generated by an
+ % appropriate .bst file with BibTeX.
+ % Author-year mode || Numerical mode
+ % Then, \citet{key} ==>> Jones et al. (1990) || Jones et al. [21]
+ % \citep{key} ==>> (Jones et al., 1990) || [21]
+ % Multiple citations as normal:
+ % \citep{key1,key2} ==>> (Jones et al., 1990; Smith, 1989) || [21,24]
+ % or (Jones et al., 1990, 1991) || [21,24]
+ % or (Jones et al., 1990a,b) || [21,24]
+ % \cite{key} is the equivalent of \citet{key} in author-year mode
+ % and of \citep{key} in numerical mode
+ % Full author lists may be forced with \citet* or \citep*, e.g.
+ % \citep*{key} ==>> (Jones, Baker, and Williams, 1990)
+ % Optional notes as:
+ % \citep[chap. 2]{key} ==>> (Jones et al., 1990, chap. 2)
+ % \citep[e.g.,][]{key} ==>> (e.g., Jones et al., 1990)
+ % \citep[see][pg. 34]{key}==>> (see Jones et al., 1990, pg. 34)
+ % (Note: in standard LaTeX, only one note is allowed, after the ref.
+ % Here, one note is like the standard, two make pre- and post-notes.)
+ % \citealt{key} ==>> Jones et al. 1990
+ % \citealt*{key} ==>> Jones, Baker, and Williams 1990
+ % \citealp{key} ==>> Jones et al., 1990
+ % \citealp*{key} ==>> Jones, Baker, and Williams, 1990
+ % Additional citation possibilities (both author-year and numerical modes)
+ % \citeauthor{key} ==>> Jones et al.
+ % \citeauthor*{key} ==>> Jones, Baker, and Williams
+ % \citeyear{key} ==>> 1990
+ % \citeyearpar{key} ==>> (1990)
+ % \citetext{priv. comm.} ==>> (priv. comm.)
+ % Note: full author lists depends on whether the bib style supports them;
+ % if not, the abbreviated list is printed even when full requested.
+ %
+ % For names like della Robbia at the start of a sentence, use
+ % \Citet{dRob98} ==>> Della Robbia (1998)
+ % \Citep{dRob98} ==>> (Della Robbia, 1998)
+ % \Citeauthor{dRob98} ==>> Della Robbia
+ %
+ %
+ % Citation aliasing is achieved with
+ % \defcitealias{key}{text}
+ % \citetalias{key} ==>> text
+ % \citepalias{key} ==>> (text)
+ %
+ % Defining the citation style of a given bib style:
+ % Use \bibpunct (in the preamble only) with 6 mandatory arguments:
+ % 1. opening bracket for citation
+ % 2. closing bracket
+ % 3. citation separator (for multiple citations in one \cite)
+ % 4. the letter n for numerical styles, s for superscripts
+ % else anything for author-year
+ % 5. punctuation between authors and date
+ % 6. punctuation between years (or numbers) when common authors missing
+ % One optional argument is the character coming before post-notes. It
+ % appears in square braces before all other arguments. May be left off.
+ % Example (and default) \bibpunct[, ]{(}{)}{;}{a}{,}{,}
+ %
+ % To make this automatic for a given bib style, named newbib, say, make
+ % a local configuration file, natbib.cfg, with the definition
+ % \newcommand{\bibstyle@newbib}{\bibpunct...}
+ % Then the \bibliographystyle{newbib} will cause \bibstyle@newbib to
+ % be called on THE NEXT LATEX RUN (via the aux file).
+ %
+ % Such preprogrammed definitions may be invoked in the text (preamble only)
+ % by calling \citestyle{newbib}. This is only useful if the style specified
+ % differs from that in \bibliographystyle.
+ %
+ % With \citeindextrue and \citeindexfalse, one can control whether the
+ % \cite commands make an automatic entry of the citation in the .idx
+ % indexing file. For this, \makeindex must also be given in the preamble.
+ %
+ % LaTeX2e Options: (for selecting punctuation)
+ % round - round parentheses are used (default)
+ % square - square brackets are used [option]
+ % curly - curly braces are used {option}
+ % angle - angle brackets are used <option>
+ % colon - multiple citations separated by colon (default)
+ % comma - separated by comma
+ % authoryear - selects author-year citations (default)
+ % numbers- selects numerical citations
+ % super - numerical citations as superscripts
+ % sort - sorts multiple citations according to order in ref. list
+ % sort&compress - like sort, but also compresses numerical citations
+ % longnamesfirst - makes first citation full author list
+ % sectionbib - puts bibliography in a \section* instead of \chapter*
+ % Punctuation so selected dominates over any predefined ones.
+ % LaTeX2e options are called as, e.g.
+ % \usepackage[square,comma]{natbib}
+ % LaTeX the source file natbib.dtx to obtain more details
+ % or the file natnotes.tex for a brief reference sheet.
+ %-----------------------------------------------------------
+\@ifclassloaded{aguplus}{\PackageError{natbib}
+ {The aguplus class already includes natbib coding,\MessageBreak
+ so you should not add it explicitly}
+ {Type <Return> for now, but then later remove\MessageBreak
+ the command \protect\usepackage{natbib} from the document}
+ \endinput}{}
+\@ifclassloaded{nlinproc}{\PackageError{natbib}
+ {The nlinproc class already includes natbib coding,\MessageBreak
+ so you should not add it explicitly}
+ {Type <Return> for now, but then later remove\MessageBreak
+ the command \protect\usepackage{natbib} from the document}
+ \endinput}{}
+\@ifclassloaded{egs}{\PackageError{natbib}
+ {The egs class already includes natbib coding,\MessageBreak
+ so you should not add it explicitly}
+ {Type <Return> for now, but then later remove\MessageBreak
+ the command \protect\usepackage{natbib} from the document}
+ \endinput}{}
+ % Define citation punctuation for some author-year styles
+ % One may add and delete at this point
+ % Or put additions into local configuration file natbib.cfg
+\newcommand\bibstyle@chicago{\bibpunct{(}{)}{;}{a}{,}{,}}
+\newcommand\bibstyle@named{\bibpunct{[}{]}{;}{a}{,}{,}}
+\newcommand\bibstyle@agu{\bibpunct{[}{]}{;}{a}{,}{,~}}%Amer. Geophys. Union
+\newcommand\bibstyle@egs{\bibpunct{(}{)}{;}{a}{,}{,}}%Eur. Geophys. Soc.
+\newcommand\bibstyle@agsm{\bibpunct{(}{)}{,}{a}{}{,}\gdef\harvardand{\&}}
+\newcommand\bibstyle@kluwer{\bibpunct{(}{)}{,}{a}{}{,}\gdef\harvardand{\&}}
+\newcommand\bibstyle@dcu{\bibpunct{(}{)}{;}{a}{;}{,}\gdef\harvardand{and}}
+\newcommand\bibstyle@aa{\bibpunct{(}{)}{;}{a}{}{,}} %Astronomy & Astrophysics
+\newcommand\bibstyle@pass{\bibpunct{(}{)}{;}{a}{,}{,}}%Planet. & Space Sci
+\newcommand\bibstyle@anngeo{\bibpunct{(}{)}{;}{a}{,}{,}}%Annales Geophysicae
+\newcommand\bibstyle@nlinproc{\bibpunct{(}{)}{;}{a}{,}{,}}%Nonlin.Proc.Geophys.
+ % Define citation punctuation for some numerical styles
+\newcommand\bibstyle@cospar{\bibpunct{/}{/}{,}{n}{}{}%
+ \gdef\NAT@biblabelnum##1{##1.}}
+\newcommand\bibstyle@esa{\bibpunct{(Ref.~}{)}{,}{n}{}{}%
+ \gdef\NAT@biblabelnum##1{##1.\hspace{1em}}}
+\newcommand\bibstyle@nature{\bibpunct{}{}{,}{s}{}{\textsuperscript{,}}%
+ \gdef\NAT@biblabelnum##1{##1.}}
+ % The standard LaTeX styles
+\newcommand\bibstyle@plain{\bibpunct{[}{]}{,}{n}{}{,}}
+\let\bibstyle@alpha=\bibstyle@plain
+\let\bibstyle@abbrv=\bibstyle@plain
+\let\bibstyle@unsrt=\bibstyle@plain
+ % The author-year modifications of the standard styles
+\newcommand\bibstyle@plainnat{\bibpunct{[}{]}{,}{a}{,}{,}}
+\let\bibstyle@abbrvnat=\bibstyle@plainnat
+\let\bibstyle@unsrtnat=\bibstyle@plainnat
+\newif\ifNAT@numbers \NAT@numbersfalse
+\newif\ifNAT@super \NAT@superfalse
+\DeclareOption{numbers}{\NAT@numberstrue
+ \ExecuteOptions{square,comma,nobibstyle}}
+\DeclareOption{super}{\NAT@supertrue\NAT@numberstrue
+ \renewcommand\NAT@open{}\renewcommand\NAT@close{}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{authoryear}{\NAT@numbersfalse
+ \ExecuteOptions{round,colon,bibstyle}}
+\DeclareOption{round}{%
+ \renewcommand\NAT@open{(} \renewcommand\NAT@close{)}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{square}{%
+ \renewcommand\NAT@open{[} \renewcommand\NAT@close{]}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{angle}{%
+ \renewcommand\NAT@open{$<$} \renewcommand\NAT@close{$>$}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{curly}{%
+ \renewcommand\NAT@open{\{} \renewcommand\NAT@close{\}}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{comma}{\renewcommand\NAT@sep{,}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{colon}{\renewcommand\NAT@sep{;}
+ \ExecuteOptions{nobibstyle}}
+\DeclareOption{nobibstyle}{\let\bibstyle=\@gobble}
+\DeclareOption{bibstyle}{\let\bibstyle=\@citestyle}
+\newif\ifNAT@openbib \NAT@openbibfalse
+\DeclareOption{openbib}{\NAT@openbibtrue}
+\DeclareOption{sectionbib}{\def\NAT@sectionbib{on}}
+\def\NAT@sort{0}
+\DeclareOption{sort}{\def\NAT@sort{1}}
+\DeclareOption{sort&compress}{\def\NAT@sort{2}}
+\@ifpackageloaded{cite}{\PackageWarningNoLine{natbib}
+ {The `cite' package should not be used\MessageBreak
+ with natbib. Use option `sort' instead}\ExecuteOptions{sort}}{}
+\newif\ifNAT@longnames\NAT@longnamesfalse
+\DeclareOption{longnamesfirst}{\NAT@longnamestrue}
+\DeclareOption{nonamebreak}{\def\NAT@nmfmt#1{\mbox{\NAT@up#1}}}
+\def\NAT@nmfmt#1{{\NAT@up#1}}
+\renewcommand\bibstyle[1]{\@ifundefined{bibstyle@#1}{\relax}
+ {\csname bibstyle@#1\endcsname}}
+\AtBeginDocument{\global\let\bibstyle=\@gobble}
+\let\@citestyle\bibstyle
+\newcommand\citestyle[1]{\@citestyle{#1}\let\bibstyle\@gobble}
+\@onlypreamble{\citestyle}\@onlypreamble{\@citestyle}
+\newcommand\bibpunct[7][, ]%
+ {\gdef\NAT@open{#2}\gdef\NAT@close{#3}\gdef
+ \NAT@sep{#4}\global\NAT@numbersfalse\ifx #5n\global\NAT@numberstrue
+ \else
+ \ifx #5s\global\NAT@numberstrue\global\NAT@supertrue
+ \fi\fi
+ \gdef\NAT@aysep{#6}\gdef\NAT@yrsep{#7}%
+ \gdef\NAT@cmt{#1}%
+ \global\let\bibstyle\@gobble
+ }
+\@onlypreamble{\bibpunct}
+\newcommand\NAT@open{(} \newcommand\NAT@close{)}
+\newcommand\NAT@sep{;}
+\ProcessOptions
+\newcommand\NAT@aysep{,} \newcommand\NAT@yrsep{,}
+\newcommand\NAT@cmt{, }
+\newcommand\NAT@cite%
+ [3]{\ifNAT@swa\NAT@@open\if*#2*\else#2\ \fi
+ #1\if*#3*\else\NAT@cmt#3\fi\NAT@@close\else#1\fi\endgroup}
+\newcommand\NAT@citenum%
+ [3]{\ifNAT@swa\NAT@@open\if*#2*\else#2\ \fi
+ #1\if*#3*\else\NAT@cmt#3\fi\NAT@@close\else#1\fi\endgroup}
+\newcommand\NAT@citesuper[3]{\ifNAT@swa
+\unskip\hspace{1\p@}\textsuperscript{#1}%
+ \if*#3*\else\ (#3)\fi\else #1\fi\endgroup}
+\providecommand
+ \textsuperscript[1]{\mbox{$^{\mbox{\scriptsize#1}}$}}
+\providecommand\@firstofone[1]{#1}
+\newcommand\NAT@citexnum{}
+\def\NAT@citexnum[#1][#2]#3{%
+ \NAT@sort@cites{#3}%
+ \let\@citea\@empty
+ \@cite{\def\NAT@num{-1}\let\NAT@last@yr\relax\let\NAT@nm\@empty
+ \@for\@citeb:=\NAT@cite@list\do
+ {\edef\@citeb{\expandafter\@firstofone\@citeb}%
+ \if@filesw\immediate\write\@auxout{\string\citation{\@citeb}}\fi
+ \@ifundefined{b@\@citeb\@extra@b@citeb}{%
+ {\reset@font\bfseries?}
+ \NAT@citeundefined\PackageWarning{natbib}%
+ {Citation `\@citeb' on page \thepage \space undefined}}%
+ {\let\NAT@last@num\NAT@num\let\NAT@last@nm\NAT@nm
+ \NAT@parse{\@citeb}%
+ \ifNAT@longnames\@ifundefined{bv@\@citeb\@extra@b@citeb}{%
+ \let\NAT@name=\NAT@all@names
+ \global\@namedef{bv@\@citeb\@extra@b@citeb}{}}{}%
+ \fi
+ \ifNAT@full\let\NAT@nm\NAT@all@names\else
+ \let\NAT@nm\NAT@name\fi
+ \ifNAT@swa
+ \ifnum\NAT@ctype>1\relax\@citea
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \ifnum\NAT@ctype=2\relax\NAT@test{\NAT@ctype}%
+ \else\NAT@alias
+ \fi\hyper@natlinkend\else
+ \ifnum\NAT@sort>1
+ \begingroup\catcode`\_=8
+ \ifcat _\ifnum\z@<0\NAT@num _\else A\fi
+ \global\let\NAT@nm=\NAT@num \else \gdef\NAT@nm{-2}\fi
+ \ifcat _\ifnum\z@<0\NAT@last@num _\else A\fi
+ \global\@tempcnta=\NAT@last@num \global\advance\@tempcnta by\@ne
+ \else \global\@tempcnta\m@ne\fi
+ \endgroup
+ \ifnum\NAT@nm=\@tempcnta
+ \ifx\NAT@last@yr\relax
+ \edef\NAT@last@yr{\@citea \mbox{\noexpand\citenumfont{\NAT@num}}}%
+ \else
+ \edef\NAT@last@yr{--\penalty\@m\mbox{\noexpand\citenumfont{\NAT@num}}}%
+ \fi
+ \else
+ \NAT@last@yr \@citea \mbox{\citenumfont{\NAT@num}}%
+ \let\NAT@last@yr\relax
+ \fi
+ \else
+ \@citea \mbox{\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ {\citenumfont{\NAT@num}}\hyper@natlinkend}%
+ \fi
+ \fi
+ \def\@citea{\NAT@sep\penalty\@m\NAT@space}%
+ \else
+ \ifcase\NAT@ctype\relax
+ \ifx\NAT@last@nm\NAT@nm \NAT@yrsep\penalty\@m\NAT@space\else
+ \@citea \NAT@test{1}\ \NAT@@open
+ \if*#1*\else#1\ \fi\fi \NAT@mbox{%
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ {\citenumfont{\NAT@num}}\hyper@natlinkend}%
+ \def\@citea{\NAT@@close\NAT@sep\penalty\@m\ }%
+ \or\@citea
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@test{\NAT@ctype}\hyper@natlinkend
+ \def\@citea{\NAT@sep\penalty\@m\ }%
+ \or\@citea
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@test{\NAT@ctype}\hyper@natlinkend
+ \def\@citea{\NAT@sep\penalty\@m\ }%
+ \or\@citea
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@alias\hyper@natlinkend
+ \def\@citea{\NAT@sep\penalty\@m\ }%
+ \fi
+ \fi
+ }}%
+ \ifnum\NAT@sort>1\relax\NAT@last@yr\fi
+ \ifNAT@swa\else\ifnum\NAT@ctype=0\if*#2*\else
+ \NAT@cmt#2\fi \NAT@@close\fi\fi}{#1}{#2}}
+\newcommand\NAT@test[1]{\ifnum#1=1 \ifx\NAT@nm\NAT@noname
+ {\reset@font\bfseries(author?)}\PackageWarning{natbib}
+ {Author undefined for citation`\@citeb'
+ \MessageBreak
+ on page \thepage}\else \NAT@nm \fi
+ \else \if\relax\NAT@date\relax
+ {\reset@font\bfseries(year?)}\PackageWarning{natbib}
+ {Year undefined for citation`\@citeb'
+ \MessageBreak
+ on page \thepage}\else \NAT@date \fi \fi}
+\let\citenumfont=\relax
+\newcommand\NAT@citex{}
+\def\NAT@citex%
+ [#1][#2]#3{%
+ \NAT@sort@cites{#3}%
+ \let\@citea\@empty
+ \@cite{\let\NAT@nm\@empty\let\NAT@year\@empty
+ \@for\@citeb:=\NAT@cite@list\do
+ {\edef\@citeb{\expandafter\@firstofone\@citeb}%
+ \if@filesw\immediate\write\@auxout{\string\citation{\@citeb}}\fi
+ \@ifundefined{b@\@citeb\@extra@b@citeb}{\@citea%
+ {\reset@font\bfseries ?}\NAT@citeundefined
+ \PackageWarning{natbib}%
+ {Citation `\@citeb' on page \thepage \space undefined}\def\NAT@date{}}%
+ {\let\NAT@last@nm=\NAT@nm\let\NAT@last@yr=\NAT@year
+ \NAT@parse{\@citeb}%
+ \ifNAT@longnames\@ifundefined{bv@\@citeb\@extra@b@citeb}{%
+ \let\NAT@name=\NAT@all@names
+ \global\@namedef{bv@\@citeb\@extra@b@citeb}{}}{}%
+ \fi
+ \ifNAT@full\let\NAT@nm\NAT@all@names\else
+ \let\NAT@nm\NAT@name\fi
+ \ifNAT@swa\ifcase\NAT@ctype
+ \if\relax\NAT@date\relax
+ \@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}\NAT@date\hyper@natlinkend
+ \else
+ \ifx\NAT@last@nm\NAT@nm\NAT@yrsep
+ \ifx\NAT@last@yr\NAT@year
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}\NAT@exlab
+ \hyper@natlinkend
+ \else\unskip\
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}\NAT@date
+ \hyper@natlinkend
+ \fi
+ \else\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}%
+ \hyper@natlinkbreak{\NAT@aysep\ }{\@citeb\@extra@b@citeb}%
+ \NAT@date\hyper@natlinkend
+ \fi
+ \fi
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}\hyper@natlinkend
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@date\hyper@natlinkend
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@alias\hyper@natlinkend
+ \fi \def\@citea{\NAT@sep\ }%
+ \else\ifcase\NAT@ctype
+ \if\relax\NAT@date\relax
+ \@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}\hyper@natlinkend
+ \else
+ \ifx\NAT@last@nm\NAT@nm\NAT@yrsep
+ \ifx\NAT@last@yr\NAT@year
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}\NAT@exlab
+ \hyper@natlinkend
+ \else\unskip\
+ \hyper@natlinkstart{\@citeb\@extra@b@citeb}\NAT@date
+ \hyper@natlinkend
+ \fi
+ \else\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}%
+ \hyper@natlinkbreak{\ \NAT@@open\if*#1*\else#1\ \fi}%
+ {\@citeb\@extra@b@citeb}%
+ \NAT@date\hyper@natlinkend\fi
+ \fi
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@nmfmt{\NAT@nm}\hyper@natlinkend
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@date\hyper@natlinkend
+ \or\@citea\hyper@natlinkstart{\@citeb\@extra@b@citeb}%
+ \NAT@alias\hyper@natlinkend
+ \fi \if\relax\NAT@date\relax\def\@citea{\NAT@sep\ }%
+ \else\def\@citea{\NAT@@close\NAT@sep\ }\fi
+ \fi
+ }}\ifNAT@swa\else\if*#2*\else\NAT@cmt#2\fi
+ \if\relax\NAT@date\relax\else\NAT@@close\fi\fi}{#1}{#2}}
+\newif\ifNAT@par \NAT@partrue
+\newcommand\NAT@@open{\ifNAT@par\NAT@open\fi}
+\newcommand\NAT@@close{\ifNAT@par\NAT@close\fi}
+\newcommand\NAT@alias{\@ifundefined{al@\@citeb\@extra@b@citeb}{%
+ {\reset@font\bfseries(alias?)}\PackageWarning{natbib}
+ {Alias undefined for citation `\@citeb'
+ \MessageBreak on page \thepage}}{\@nameuse{al@\@citeb\@extra@b@citeb}}}
+\let\NAT@up\relax
+\newcommand\NAT@Up[1]{{\let\protect\@unexpandable@protect\let~\relax
+ \expandafter\NAT@deftemp#1}\expandafter\NAT@UP\NAT@temp}
+\newcommand\NAT@deftemp[1]{\xdef\NAT@temp{#1}}
+\newcommand\NAT@UP[1]{\let\@tempa\NAT@UP\ifcat a#1\MakeUppercase{#1}%
+ \let\@tempa\relax\else#1\fi\@tempa}
+\newcommand\shortcites[1]{%
+ \@bsphack\@for\@citeb:=#1\do
+ {\edef\@citeb{\expandafter\@firstofone\@citeb}%
+ \global\@namedef{bv@\@citeb\@extra@b@citeb}{}}\@esphack}
+\newcommand\NAT@biblabel[1]{\hfill}
+\newcommand\NAT@biblabelnum[1]{\bibnumfmt{#1}}
+\newcommand\bibnumfmt[1]{[#1]}
+\def\@tempa#1{[#1]}
+\ifx\@tempa\@biblabel\let\@biblabel\@empty\fi
+\newcommand\NAT@bibsetnum[1]{\settowidth\labelwidth{\@biblabel{#1}}%
+ \setlength{\leftmargin}{\labelwidth}\addtolength{\leftmargin}{\labelsep}%
+ \setlength{\itemsep}{\bibsep}\setlength{\parsep}{\z@}%
+ \ifNAT@openbib
+ \addtolength{\leftmargin}{4mm}%
+ \setlength{\itemindent}{-4mm}%
+ \setlength{\listparindent}{\itemindent}%
+ \setlength{\parsep}{0pt}%
+ \fi
+}
+\newlength{\bibhang}
+\setlength{\bibhang}{1em}
+\newlength{\bibsep}
+{\@listi \global\bibsep\itemsep \global\advance\bibsep by\parsep}
+
+\newcommand\NAT@bibsetup%
+ [1]{\setlength{\leftmargin}{\bibhang}\setlength{\itemindent}{-\leftmargin}%
+ \setlength{\itemsep}{\bibsep}\setlength{\parsep}{\z@}}
+\newcommand\NAT@set@cites{\ifNAT@numbers
+ \ifNAT@super \let\@cite\NAT@citesuper
+ \def\NAT@mbox##1{\unskip\nobreak\hspace{1\p@}\textsuperscript{##1}}%
+ \let\citeyearpar=\citeyear
+ \let\NAT@space\relax\else
+ \let\NAT@mbox=\mbox
+ \let\@cite\NAT@citenum \def\NAT@space{ }\fi
+ \let\@citex\NAT@citexnum
+ \ifx\@biblabel\@empty\let\@biblabel\NAT@biblabelnum\fi
+ \let\@bibsetup\NAT@bibsetnum
+ \def\natexlab##1{}%
+ \else
+ \let\@cite\NAT@cite
+ \let\@citex\NAT@citex
+ \let\@biblabel\NAT@biblabel
+ \let\@bibsetup\NAT@bibsetup
+ \def\natexlab##1{##1}%
+ \fi}
+\AtBeginDocument{\NAT@set@cites}
+\AtBeginDocument{\ifx\SK@def\@undefined\else
+\ifx\SK@cite\@empty\else
+ \SK@def\@citex[#1][#2]#3{\SK@\SK@@ref{#3}\SK@@citex[#1][#2]{#3}}\fi
+\ifx\SK@citeauthor\@undefined\def\HAR@checkdef{}\else
+ \let\citeauthor\SK@citeauthor
+ \let\citefullauthor\SK@citefullauthor
+ \let\citeyear\SK@citeyear\fi
+\fi}
+\AtBeginDocument{\@ifpackageloaded{hyperref}{%
+ \ifnum\NAT@sort=2\def\NAT@sort{1}\fi}{}}
+\newif\ifNAT@full\NAT@fullfalse
+\newif\ifNAT@swa
+\DeclareRobustCommand\citet
+ {\begingroup\NAT@swafalse\def\NAT@ctype{0}\NAT@partrue
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\newcommand\NAT@citetp{\@ifnextchar[{\NAT@@citetp}{\NAT@@citetp[]}}
+\newcommand\NAT@@citetp{}
+\def\NAT@@citetp[#1]{\@ifnextchar[{\@citex[#1]}{\@citex[][#1]}}
+\DeclareRobustCommand\citep
+ {\begingroup\NAT@swatrue\def\NAT@ctype{0}\NAT@partrue
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\cite
+ {\begingroup\def\NAT@ctype{0}\NAT@partrue\NAT@swatrue
+ \@ifstar{\NAT@fulltrue\NAT@cites}{\NAT@fullfalse\NAT@cites}}
+\newcommand\NAT@cites{\@ifnextchar [{\NAT@@citetp}{%
+ \ifNAT@numbers\else
+ \NAT@swafalse
+ \fi
+ \NAT@@citetp[]}}
+\DeclareRobustCommand\citealt
+ {\begingroup\NAT@swafalse\def\NAT@ctype{0}\NAT@parfalse
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\citealp
+ {\begingroup\NAT@swatrue\def\NAT@ctype{0}\NAT@parfalse
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\citeauthor
+ {\begingroup\NAT@swafalse\def\NAT@ctype{1}\NAT@parfalse
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\Citet
+ {\begingroup\NAT@swafalse\def\NAT@ctype{0}\NAT@partrue
+ \let\NAT@up\NAT@Up
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\Citep
+ {\begingroup\NAT@swatrue\def\NAT@ctype{0}\NAT@partrue
+ \let\NAT@up\NAT@Up
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\Citealt
+ {\begingroup\NAT@swafalse\def\NAT@ctype{0}\NAT@parfalse
+ \let\NAT@up\NAT@Up
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\Citealp
+ {\begingroup\NAT@swatrue\def\NAT@ctype{0}\NAT@parfalse
+ \let\NAT@up\NAT@Up
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\Citeauthor
+ {\begingroup\NAT@swafalse\def\NAT@ctype{1}\NAT@parfalse
+ \let\NAT@up\NAT@Up
+ \@ifstar{\NAT@fulltrue\NAT@citetp}{\NAT@fullfalse\NAT@citetp}}
+\DeclareRobustCommand\citeyear
+ {\begingroup\NAT@swafalse\def\NAT@ctype{2}\NAT@parfalse\NAT@citetp}
+\DeclareRobustCommand\citeyearpar
+ {\begingroup\NAT@swatrue\def\NAT@ctype{2}\NAT@partrue\NAT@citetp}
+\newcommand\citetext[1]{\NAT@open#1\NAT@close}
+\DeclareRobustCommand\citefullauthor
+ {\citeauthor*}
+\newcommand\defcitealias[2]{%
+ \@ifundefined{al@#1\@extra@b@citeb}{}
+ {\PackageWarning{natbib}{Overwriting existing alias for citation #1}}
+ \@namedef{al@#1\@extra@b@citeb}{#2}}
+\DeclareRobustCommand\citetalias{\begingroup
+ \NAT@swafalse\def\NAT@ctype{3}\NAT@parfalse\NAT@citetp}
+\DeclareRobustCommand\citepalias{\begingroup
+ \NAT@swatrue\def\NAT@ctype{3}\NAT@partrue\NAT@citetp}
+\renewcommand\nocite[1]{\@bsphack
+ \@for\@citeb:=#1\do{%
+ \edef\@citeb{\expandafter\@firstofone\@citeb}%
+ \if@filesw\immediate\write\@auxout{\string\citation{\@citeb}}\fi
+ \if*\@citeb\else
+ \@ifundefined{b@\@citeb\@extra@b@citeb}{%
+ \NAT@citeundefined \PackageWarning{natbib}%
+ {Citation `\@citeb' undefined}}{}\fi}%
+ \@esphack}
+\newcommand\NAT@parse[1]{{%
+ \let\protect=\@unexpandable@protect\let~\relax
+ \let\active@prefix=\@gobble
+ \xdef\NAT@temp{\csname b@#1\@extra@b@citeb\endcsname}}%
+ \expandafter\NAT@split\NAT@temp
+ \expandafter\NAT@parse@date\NAT@date??????@@%
+ \ifciteindex\NAT@index\fi
+}
+\newcommand\NAT@split[4]{%
+ \gdef\NAT@num{#1}\gdef\NAT@name{#3}\gdef\NAT@date{#2}%
+ \gdef\NAT@all@names{#4}%
+ \ifx\NAT@noname\NAT@all@names \gdef\NAT@all@names{#3}\fi}
+\newcommand\NAT@parse@date{}
+\def\NAT@parse@date#1#2#3#4#5#6@@{%
+ \ifnum\the\catcode`#1=11\def\NAT@year{}\def\NAT@exlab{#1}\else
+ \ifnum\the\catcode`#2=11\def\NAT@year{#1}\def\NAT@exlab{#2}\else
+ \ifnum\the\catcode`#3=11\def\NAT@year{#1#2}\def\NAT@exlab{#3}\else
+ \ifnum\the\catcode`#4=11\def\NAT@year{#1#2#3}\def\NAT@exlab{#4}\else
+ \def\NAT@year{#1#2#3#4}\def\NAT@exlab{{#5}}\fi\fi\fi\fi}
+\newcommand\NAT@index{}
+\let\NAT@makeindex=\makeindex
+\renewcommand\makeindex{\NAT@makeindex
+ \renewcommand\NAT@index{\@bsphack\begingroup
+ \def~{\string~}\@wrindex{\NAT@idxtxt}}}
+\newcommand\NAT@idxtxt{\NAT@name\ \NAT@open\NAT@date\NAT@close}
+\@ifundefined{@indexfile}{}{\let\NAT@makeindex\relax\makeindex}
+\newif\ifciteindex \citeindexfalse
+\newcommand\citeindextype{default}
+\newcommand\NAT@index@alt{{\let\protect=\noexpand\let~\relax
+ \xdef\NAT@temp{\NAT@idxtxt}}\expandafter\NAT@exp\NAT@temp\@nil}
+\newcommand\NAT@exp{}
+\def\NAT@exp#1\@nil{\mbox{}\index[\citeindextype]{#1}}
+
+\AtBeginDocument{%
+\@ifpackageloaded{index}{\let\NAT@index=\NAT@index@alt}{}}
+\newcommand\NAT@ifcmd{\futurelet\NAT@temp\NAT@ifxcmd}
+\newcommand\NAT@ifxcmd{\ifx\NAT@temp\relax\else\expandafter\NAT@bare\fi}
+\def\NAT@bare#1(#2)#3(@)#4\@nil#5{%
+ \if @#2
+ \expandafter\NAT@apalk#1, , \@nil{#5}\else
+ \stepcounter{NAT@ctr}%
+ \NAT@wrout{\arabic {NAT@ctr}}{#2}{#1}{#3}{#5}
+\fi
+}
+\newcommand\NAT@wrout[5]{%
+\if@filesw
+ {\let\protect\noexpand\let~\relax
+ \immediate
+ \write\@auxout{\string\bibcite{#5}{{#1}{#2}{{#3}}{{#4}}}}}\fi
+\ignorespaces}
+\def\NAT@noname{{}}
+\renewcommand\bibitem{%
+ \@ifnextchar[{\@lbibitem}{%
+ \global\NAT@stdbsttrue
+ \stepcounter{NAT@ctr}\@lbibitem[\arabic{NAT@ctr}]}}
+\def\@lbibitem[#1]#2{%
+ \if\relax\@extra@b@citeb\relax\else
+ \@ifundefined{br@#2\@extra@b@citeb}{}{%
+ \@namedef{br@#2}{\@nameuse{br@#2\@extra@b@citeb}}}\fi
+ \@ifundefined{b@#2\@extra@b@citeb}{\def\NAT@num{}}{\NAT@parse{#2}}%
+ \item[\hfil\hyper@natanchorstart{#2\@extra@b@citeb}\@biblabel{\NAT@num}%
+ \hyper@natanchorend]%
+ \NAT@ifcmd#1(@)(@)\@nil{#2}}
+\ifx\SK@lbibitem\@undefined\else
+ \let\SK@lbibitem\@lbibitem
+ \def\@lbibitem[#1]#2{%
+ \SK@lbibitem[#1]{#2}\SK@\SK@@label{#2}\ignorespaces}\fi
+\newif\ifNAT@stdbst \NAT@stdbstfalse
+
+\AtEndDocument
+ {\ifNAT@stdbst\if@filesw\immediate\write\@auxout{\string
+ \global\string\NAT@numberstrue}\fi\fi
+ }
+\providecommand\bibcite{}
+\renewcommand\bibcite[2]{\@ifundefined{b@#1\@extra@binfo}\relax
+ {\NAT@citemultiple
+ \PackageWarningNoLine{natbib}{Citation `#1' multiply defined}}%
+ \global\@namedef{b@#1\@extra@binfo}{#2}}
+\AtEndDocument{\NAT@swatrue\let\bibcite\NAT@testdef}
+\newcommand\NAT@testdef[2]{%
+ \def\NAT@temp{#2}\expandafter \ifx \csname b@#1\@extra@binfo\endcsname
+ \NAT@temp \else \ifNAT@swa \NAT@swafalse
+ \PackageWarningNoLine{natbib}{Citation(s) may have
+ changed.\MessageBreak
+ Rerun to get citations correct}\fi\fi}
+\newcommand\NAT@apalk{}
+\def\NAT@apalk#1, #2, #3\@nil#4{\if\relax#2\relax
+ \global\NAT@stdbsttrue
+ \NAT@wrout{#1}{}{}{}{#4}\else
+ \stepcounter{NAT@ctr}%
+ \NAT@wrout{\arabic {NAT@ctr}}{#2}{#1}{}{#4}\fi}
+\newcommand\citeauthoryear{}
+\def\citeauthoryear#1#2#3(@)(@)\@nil#4{\stepcounter{NAT@ctr}\if\relax#3\relax
+ \NAT@wrout{\arabic {NAT@ctr}}{#2}{#1}{}{#4}\else
+ \NAT@wrout{\arabic {NAT@ctr}}{#3}{#2}{#1}{#4}\fi}
+\newcommand\citestarts{\NAT@open}
+\newcommand\citeends{\NAT@close}
+\newcommand\betweenauthors{and}
+\newcommand\astroncite{}
+\def\astroncite#1#2(@)(@)\@nil#3{\stepcounter{NAT@ctr}\NAT@wrout{\arabic
+{NAT@ctr}}{#2}{#1}{}{#3}}
+\newcommand\citename{}
+\def\citename#1#2(@)(@)\@nil#3{\expandafter\NAT@apalk#1#2, \@nil{#3}}
+\newcommand\harvarditem[4][]%
+ {\if\relax#1\relax\bibitem[#2(#3)]{#4}\else
+ \bibitem[#1(#3)#2]{#4}\fi }
+\newcommand\harvardleft{\NAT@open}
+\newcommand\harvardright{\NAT@close}
+\newcommand\harvardyearleft{\NAT@open}
+\newcommand\harvardyearright{\NAT@close}
+\AtBeginDocument{\providecommand{\harvardand}{and}}
+\newcommand\harvardurl[1]{\textbf{URL:} \textit{#1}}
+\providecommand\bibsection{}
+\@ifundefined{chapter}%
+ {\renewcommand\bibsection{\section*{\refname
+ \@mkboth{\MakeUppercase{\refname}}{\MakeUppercase{\refname}}}}}
+ {\@ifundefined{NAT@sectionbib}%
+ {\renewcommand\bibsection{\chapter*{\bibname
+ \@mkboth{\MakeUppercase{\bibname}}{\MakeUppercase{\bibname}}}}}
+ {\renewcommand\bibsection{\section*{\bibname
+ \ifx\@mkboth\@gobbletwo\else\markright{\MakeUppercase{\bibname}}\fi}}}}
+\@ifclassloaded{amsart}%
+ {\renewcommand\bibsection{\section*{\refname}}}{}
+\@ifclassloaded{amsbook}%
+ {\renewcommand\bibsection{\chapter*{\bibname}}}{}
+\@ifundefined{bib@heading}{}{\let\bibsection\bib@heading}
+\newcounter{NAT@ctr}
+\renewenvironment{thebibliography}[1]{%
+ \bibsection
+ \vspace{1\p@}\parindent \z@\bibpreamble\bibfont\list
+ {\@biblabel{\arabic{NAT@ctr}}}{\@bibsetup{#1}%
+ \setcounter{NAT@ctr}{0}}%
+ \ifNAT@openbib
+ \renewcommand\newblock{\par}
+ \else
+ \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%
+ \fi
+ \sloppy\clubpenalty4000\widowpenalty4000
+ \sfcode`\.=1000\relax
+ \let\citeN\cite \let\shortcite\cite
+ \let\citeasnoun\cite\fontsize{7}{9}\selectfont
+ }{\def\@noitemerr{%
+ \PackageWarning{natbib}
+ {Empty `thebibliography' environment}}%
+ \endlist\vskip-\lastskip}
+\let\bibfont\relax
+\let\bibpreamble\relax
+\providecommand\reset@font{\relax}
+\providecommand\bibname{Bibliography}
+\providecommand\refname{References}
+\newcommand\NAT@citeundefined{\gdef \NAT@undefined {%
+ \PackageWarningNoLine{natbib}{There were undefined citations}}}
+\let \NAT@undefined \relax
+\newcommand\NAT@citemultiple{\gdef \NAT@multiple {%
+ \PackageWarningNoLine{natbib}{There were multiply defined citations}}}
+\let \NAT@multiple \relax
+\AtEndDocument{\NAT@undefined\NAT@multiple}
+\providecommand\@mkboth[2]{}
+\providecommand\MakeUppercase{\uppercase}
+\providecommand{\@extra@b@citeb}{}
+\gdef\@extra@binfo{}
+\providecommand\hyper@natanchorstart[1]{}
+\providecommand\hyper@natanchorend{}
+\providecommand\hyper@natlinkstart[1]{}
+\providecommand\hyper@natlinkend{}
+\providecommand\hyper@natlinkbreak[2]{#1}
+\@ifundefined{bbl@redefine}{}{%
+ \bbl@redefine\nocite#1{%
+ \@safe@activestrue\org@nocite{#1}\@safe@activesfalse}%
+\bbl@redefine\@lbibitem[#1]#2{%
+ \@safe@activestrue\org@@lbibitem[#1]{#2}\@safe@activesfalse}%
+}
+\AtBeginDocument{\@ifundefined{bbl@redefine}{}{%
+\bbl@redefine\@citex[#1][#2]#3{%
+ \@safe@activestrue\org@@citex[#1][#2]{#3}\@safe@activesfalse}%
+\bbl@redefine\NAT@testdef#1#2{%
+ \@safe@activestrue\org@NAT@testdef{#1}{#2}\@safe@activesfalse}%
+\@ifundefined{org@@lbibitem}{%
+\bbl@redefine\@lbibitem[#1]#2{%
+ \@safe@activestrue\org@@lbibitem[#1]{#2}\@safe@activesfalse}}{}%
+}}
+\ifnum\NAT@sort>0
+\newcommand\NAT@sort@cites[1]{%
+\@tempcntb\m@ne
+\let\@celt\delimiter
+\def\NAT@num@list{}%
+\def\NAT@cite@list{}%
+\def\NAT@nonsort@list{}%
+\@for \@citeb:=#1\do{\NAT@make@cite@list}%
+\edef\NAT@cite@list{\NAT@cite@list\NAT@nonsort@list}%
+\edef\NAT@cite@list{\expandafter\NAT@xcom\NAT@cite@list @@}}
+\begingroup \catcode`\_=8
+\gdef\NAT@make@cite@list{%
+ \edef\@citeb{\expandafter\@firstofone\@citeb}%
+ \@ifundefined{b@\@citeb\@extra@b@citeb}{\def\NAT@num{A}}%
+ {\NAT@parse{\@citeb}}%
+ \ifcat _\ifnum\z@<0\NAT@num _\else A\fi
+ \@tempcnta\NAT@num \relax
+ \ifnum \@tempcnta>\@tempcntb
+ \edef\NAT@num@list{\NAT@num@list \@celt{\NAT@num}}%
+ \edef\NAT@cite@list{\NAT@cite@list\@citeb,}%
+ \@tempcntb\@tempcnta
+ \else
+ \let\NAT@@cite@list=\NAT@cite@list \def\NAT@cite@list{}%
+ \edef\NAT@num@list{\expandafter\NAT@num@celt \NAT@num@list \@gobble @}%
+ {\let\@celt=\NAT@celt\NAT@num@list}%
+ \fi
+ \else
+ \edef\NAT@nonsort@list{\NAT@nonsort@list\@citeb,}%
+ \fi}
+\endgroup
+\def\NAT@celt#1{\ifnum #1<\@tempcnta
+ \xdef\NAT@cite@list{\NAT@cite@list\expandafter\NAT@nextc\NAT@@cite@list @@}%
+ \xdef\NAT@@cite@list{\expandafter\NAT@restc\NAT@@cite@list}%
+ \else
+ \xdef\NAT@cite@list{\NAT@cite@list\@citeb,\NAT@@cite@list}\let\@celt\@gobble%
+ \fi}
+\def\NAT@num@celt#1#2{\ifx \@celt #1%
+ \ifnum #2<\@tempcnta
+ \@celt{#2}%
+ \expandafter\expandafter\expandafter\NAT@num@celt
+ \else
+ \@celt{\number\@tempcnta}\@celt{#2}%
+ \fi\fi}
+\def\NAT@nextc#1,#2@@{#1,}
+\def\NAT@restc#1,#2{#2}
+\def\NAT@xcom#1,@@{#1}
+\else
+ \newcommand\NAT@sort@cites[1]{\edef\NAT@cite@list{#1}}\fi
+\InputIfFileExists{natbib.cfg}
+ {\typeout{Local config file natbib.cfg used}}{}
+%%
+%% <<<<< End of generated file <<<<<<
+%%
+%% End of file `natbib.sty'.
diff --git a/tex/order_eval.js b/tex/order_eval.js
new file mode 100644
index 0000000..e6561b4
--- /dev/null
+++ b/tex/order_eval.js
@@ -0,0 +1,129 @@
+var getopt = function(args, ostr) {
+ var oli; // option letter list index
+ if (typeof(getopt.place) == 'undefined')
+ getopt.ind = 0, getopt.arg = null, getopt.place = -1;
+ if (getopt.place == -1) { // update scanning pointer
+ if (getopt.ind >= args.length || args[getopt.ind].charAt(getopt.place = 0) != '-') {
+ getopt.place = -1;
+ return null;
+ }
+ if (getopt.place + 1 < args[getopt.ind].length && args[getopt.ind].charAt(++getopt.place) == '-') { // found "--"
+ ++getopt.ind;
+ getopt.place = -1;
+ return null;
+ }
+ }
+ var optopt = args[getopt.ind].charAt(getopt.place++); // character checked for validity
+ if (optopt == ':' || (oli = ostr.indexOf(optopt)) < 0) {
+ if (optopt == '-') return null; // if the user didn't specify '-' as an option, assume it means null.
+ if (getopt.place < 0) ++getopt.ind;
+ return '?';
+ }
+ if (oli+1 >= ostr.length || ostr.charAt(++oli) != ':') { // don't need argument
+ getopt.arg = null;
+ if (getopt.place < 0 || getopt.place >= args[getopt.ind].length) ++getopt.ind, getopt.place = -1;
+ } else { // need an argument
+ if (getopt.place >= 0 && getopt.place < args[getopt.ind].length)
+ getopt.arg = args[getopt.ind].substr(getopt.place);
+ else if (args.length <= ++getopt.ind) { // no arg
+ getopt.place = -1;
+ if (ostr.length > 0 && ostr.charAt(0) == ':') return ':';
+ return '?';
+ } else getopt.arg = args[getopt.ind]; // white space
+ getopt.place = -1;
+ ++getopt.ind;
+ }
+ return optopt;
+}
+
+var c, ws = 5, min_span = 2000;
+
+while ((c = getopt(arguments, "w:s:")) != null)
+ if (c == 'w') ws = parseInt(getopt.arg);
+ else if (c == 's') min_span = parseInt(getopt.arg);
+
+if (arguments.length - getopt.ind < 2) {
+ print("Usage: k8 cmp_order.js <gfa2bed.bed> <paftop>");
+ exit(1);
+}
+
+var b = new Bytes();
+
+var bed = [], h = {}, end = {}, last_u = null, last_r = null, to_end = 0;
+var f = new File(arguments[getopt.ind]);
+while (f.readline(b) >= 0) {
+ var t = b.toString().split("\t");
+ var r = t[0] + ":" + (parseInt(t[1]) + 1) + "-" + t[2];
+ h[r] = bed.length;
+ if (to_end > 0) end[r] = 1, --to_end;
+ if (last_u == null || t[3] != last_u) {
+ end[r] = 1, to_end = ws - 1;
+ if (last_r != null) {
+ end[last_r] = 1;
+ for (var j = bed.length - 1; j >= 0 && j >= bed.length - ws; --j)
+ end[bed[j][2]] = 1;
+ }
+ }
+ var center = Math.floor(parseInt(t[5]) + (parseInt(t[2]) - parseInt(t[1])) / 2);
+ bed.push([t[3], t[4], r, center]);
+ last_r = r; last_u = t[3];
+}
+end[last_r] = 1;
+for (var j = bed.length - 1; j >= 0 && j >= bed.length - ws; --j)
+ end[bed[j][2]] = 1;
+f.close();
+
+var paf = [];
+f = new File(arguments[getopt.ind+1]);
+while (f.readline(b) >= 0) {
+ var t = b.toString().split("\t");
+ if (parseInt(t[3]) - parseInt(t[2]) < min_span) continue; // a tiny hit
+ if (paf.length && t[0] == paf[paf.length - 1][0]) continue; // dup
+ var center;
+ t[1] = parseInt(t[1]);
+ t[2] = parseInt(t[2]); t[3] = parseInt(t[3]);
+ t[8] = parseInt(t[8]); t[9] = parseInt(t[9]);
+ if (t[4] == '+') {
+ center = Math.floor(((t[7] - t[2]) + (t[8] + (t[1] - t[3]))) / 2);
+ } else {
+ center = Math.floor(((t[7] - (t[1] - t[3])) + (t[8] + t[2])) / 2);
+ }
+ paf.push([t[0], t[5], t[4], parseInt(t[7]), center]);
+}
+f.close();
+
+paf.sort(function(x,y){return x[1]<y[1]?-1:x[1]>y[1]?1:x[3]-y[3]});
+
+var chr_se = {}, start = 0;
+for (var i = 1; i <= paf.length; ++i) {
+ if (i == paf.length || paf[i][1] != paf[i-1][1]) {
+ chr_se[paf[i-1][1]] = [start, i];
+ start = i;
+ }
+}
+
+var cnt = 0;
+for (var k in chr_se) {
+ var st = chr_se[k][0], en = chr_se[k][1];
+ for (var i = st + ws + 1; i < en - ws - 1; ++i) {
+ var j;
+ for (j = i - 1; j >= 0; --j)
+ if (paf[i][0] != paf[j][0])
+ break;
+ if (j < 0) continue; // the first read has multiple mappings
+ if (paf[i][1] != paf[j][1]) continue; // different reference chr
+ var hi = h[paf[i][0]], hj = h[paf[j][0]];
+ var paf_diff = paf[i][4] - paf[j][4];
+ var bed_diff = bed[hi][0] == bed[hj][0]? Math.abs(bed[hi][3] - bed[hj][3]) : '*';
+ if (hi - hj > ws || hj - hi > ws || bed[hi][0] != bed[hj][0]) {
+ if (end[paf[i][0]] != null && end[paf[j][0]] != null) continue;
+ if (bed_diff != '*' && Math.abs(paf_diff - bed_diff) < min_span) continue;
+ print("E", paf[j][1], bed[hi][0] != bed[hj][0]? '*' : hi-hj, paf_diff, bed_diff, bed[hj][0], bed[hi][0], paf[j][0], paf[i][0]);
+ ++cnt;
+ }
+ }
+}
+
+print("C", cnt);
+
+b.destroy();
diff --git a/tex/overhang.pdf b/tex/overhang.pdf
new file mode 100644
index 0000000..995c041
Binary files /dev/null and b/tex/overhang.pdf differ
diff --git a/tex/paf_srtcmp.js b/tex/paf_srtcmp.js
new file mode 100644
index 0000000..5310175
--- /dev/null
+++ b/tex/paf_srtcmp.js
@@ -0,0 +1,85 @@
+if (arguments.length != 2) {
+ print("Usage: k8 paf_srtcmp.js <bwamem.srt.paf> <minimap.srt.paf>");
+ exit(1);
+}
+
+function read1(f, buf, last)
+{
+ var a = [], l = null;
+ if (last != null) a.push(last);
+ while (f.readline(buf) >= 0) {
+ var t = buf.toString().split("\t");
+ for (var j = 1; j <= 3; ++j) t[j] = parseInt(t[j]);
+ for (var j = 6; j <= 11; ++j) t[j] = parseInt(t[j]);
+ if (last == null) {
+ last = t;
+ a.push(t);
+ } else if (last[0] != t[0]) {
+ l = t;
+ break;
+ } else a.push(t);
+ }
+// if (a.length > 0) print(a[0][0], a.length);
+ return [a, l];
+}
+
+var buf = new Bytes();
+var fb = new File(arguments[0]);
+var fm = new File(arguments[1]);
+
+var tot = 0, matched = 0;
+
+var sb = read1(fb, buf, null);
+var sm = read1(fm, buf, null);
+
+function sync()
+{
+// print("here!");
+ while (sb[0][0][0] != sm[0][0][0]) {
+ if (sb[0][0][0] < sm[0][0][0]) {
+ if (sb[0].length == 1) ++tot;
+ sb = read1(fb, buf, sb[1]);
+ if (sb[0].length == 0) break;
+ } else if (sb[0][0][0] > sm[0][0][0]) {
+ sm = read1(fm, buf, sm[1]);
+ if (sm[0].length == 0) break;
+ }
+ }
+}
+
+while (1) {
+ sync();
+ if (sb[0].length == 0) break;
+ if (sm[0].length == 0) {
+ while (sb[0].length) {
+ if (sb[0].length == 1) ++tot;
+ sb = read1(fb, buf, sb[1]);
+ }
+ break;
+ }
+ if (sb[0].length == 1) {
+ var end = sm[0].length, hit = 0;
+ ++tot;
+ for (var j = 0; j < end; ++j) {
+ if (sb[0][0][4] != sm[0][j][4] || sb[0][0][5] != sm[0][j][5]) continue;
+ if (sb[0][0][8] > sm[0][j][7] && sm[0][j][8] > sb[0][0][7]) {
+ var ol, ml;
+ ol = sb[0][0][8] - sm[0][j][7];
+ ml = sm[0][j][8] - sb[0][0][7];
+ var r = ol < ml? ol / ml : ml / ol;
+ if (r >= .3333) ++matched, hit = 1;
+ break;
+ }
+ }
+ if (hit == 0) print(sb[0][0].join("\t"));
+ }
+ sb = read1(fb, buf, sb[1]);
+ sm = read1(fm, buf, sm[1]);
+ if (sb[0].length == 0) break;
+}
+
+fb.close();
+fm.close();
+buf.destroy();
+
+print(tot, matched, matched/tot);
diff --git a/tex/ref2ovlp.js b/tex/ref2ovlp.js
new file mode 100644
index 0000000..8530d68
--- /dev/null
+++ b/tex/ref2ovlp.js
@@ -0,0 +1,30 @@
+var min_l = 2000, min_q = 10;
+
+var file = arguments.length? new File(arguments[0]) : new File();
+var buf = new Bytes();
+
+var a = [];
+while (file.readline(buf) >= 0) {
+ var t = buf.toString().split("\t");
+ for (var j = 1; j <= 3; ++j) t[j] = parseInt(t[j]);
+ for (var j = 6; j <= 11; ++j) t[j] = parseInt(t[j]);
+ if (t[1] < min_l || t[11] < min_q) continue;
+ var st = 0;
+ for (var i = 0; i < a.length; ++i) {
+ if (t[7] + min_l >= a[i][8]) {
+ a[i] = null;
+ } else if (t[8] <= a[i][8]) {
+ print(t[0], a[i][0], -1);
+ } else {
+ print(t[0], a[i][0], a[i][8] - t[7]);
+ }
+ }
+ var n = 0;
+ for (var i = 0; i < a.length; ++i)
+ if (a[i] != null) a[n++] = a[i];
+ a.length = n;
+ a.push(t);
+}
+
+buf.destroy();
+file.close();
diff --git a/tex/test-sen.pl b/tex/test-sen.pl
new file mode 100755
index 0000000..470d8ae
--- /dev/null
+++ b/tex/test-sen.pl
@@ -0,0 +1,25 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+my $fn = shift(@ARGV);
+open(FH, $fn =~ /\.gz$/? "gzip -dc $fn|" : $fn) || die;
+my %h;
+while (<FH>) {
+ my @t = split;
+ $h{"$t[0]\t$t[1]"} = 1;
+}
+close(FH);
+
+while (<>) {
+ my @t = split;
+ $h{"$t[0]\t$t[5]"} = 2 if ($h{"$t[0]\t$t[5]"});
+ $h{"$t[5]\t$t[0]"} = 2 if ($h{"$t[5]\t$t[0]"});
+}
+
+my @cnt = (0, 0);
+for my $x (keys %h) {
+ ++$cnt[$h{$x}-1];
+}
+print("$cnt[0]\t$cnt[1]\t", $cnt[1]/($cnt[0]+$cnt[1]), "\n");
Debdiff
[The following lists of changes regard files as different if they have different names, permissions or owners.]
Files in second set of .debs but not in first
-rw-r--r-- root/root /usr/lib/debug/.build-id/87/bf74f26416373b75735b18ff810394606e2375.debug
Files in first set of .debs but not in second
-rw-r--r-- root/root /usr/lib/debug/.build-id/12/ab46d5fcd031c1050b21f44f1ebd1ce7cdc679.debug
No differences were encountered between the control files of package miniasm
Control files of package miniasm-dbgsym: lines which differ (wdiff format)
Build-Ids: 12ab46d5fcd031c1050b21f44f1ebd1ce7cdc679 87bf74f26416373b75735b18ff810394606e2375