Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 | 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 13018x 13018x 13018x 14x 14x 3x 10x 10x 3x 3x 3x 14x 13018x 13018x 2x 12980x 12980x 12980x 1839x 9810x 9802x 9777x 9362x 8630x 8630x 12980x 91x 91x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 1254x 1254x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 8160x 8160x 1983x 1983x 8160x 1983x 1983x 2x 2x 2x 2x 24x 24x 36x 12x 12x 24x 36x 36x 9x 9x 2x 7167x 7167x 7167x 6393x 6393x 2x 488x 488x 488x 488x 488x 488x 488x 488x 488x 488x 488x 7308x 7308x 7308x 7308x 2x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 5672x 15x 15x 15x 15x 15x 15x 15x 15x 5657x 5672x 5672x 5672x 5672x 134x 134x 134x 5523x 5672x 29x 29x 29x 29x 15x 15x 15x 15x 15x 15x 15x 14x 14x 5672x 10x 10x 10x 5672x 574x 574x 574x 4910x 5672x 45x 45x 45x 45x 45x 45x 45x 45x 4865x 5660x 5x 5x 5x 5x 5x 5x 5672x 130x 130x 5659x 506x 506x 490x 490x 490x 506x 4240x 4240x 656x 656x 656x 151x 151x 151x 285x 285x 151x 151x 237x 237x 237x 237x 2x 2x 2x 373x 373x 373x 373x 373x 373x 2x 373x 373x 373x 5234x 5234x 5234x 5234x 5234x 373x 2x 221x 221x 2x 152x 152x 2x 72x 72x 46x 46x 23x 23x 72x 72x 72x 2x 2x 428x 428x 428x 81x 81x 81x 81x 81x 81x 81x 347x 428x 5x 5x 5x 5x 5x 5x 5x 375x 428x 428x 325x 141x 141x 33x 33x 141x 168x 428x 2x 375x 375x 154x 368x 151x 151x 151x 20x 6x 375x 375x 375x 375x 375x 375x 375x 2x 154x 154x 154x 4x 154x 154x 10468x 10468x 10468x 7x 10468x 2x 7x 6x 6x 6x 6x 7x 44x 44x 3x 3x 3x 41x 38x 14x 44x 6x 7x 7x 7x 7x 7x 7x 7x 2x 71x 71x 71x 71x 71x 71x 71x 149x 149x 149x 71x 71x 71x 71x 86x 86x 86x 86x 86x 86x 86x 86x 71x 71x 71x 71x 86x 86x 86x 86x 86x 86x 86x 71x 71x 71x 71x 71x 2x 64x 64x 64x 64x 64x 64x 120x 120x 58x 58x 64x 64x 120x 120x 64x 64x 2x 31x 31x 2x 255x 255x 255x 255x 255x 255x 44x 255x 255x 2x 255x 255x 255x 181x 181x 585x 585x 181x 181x 181x 181x 2x 2x 2x 2x 2x 2x 1x 2x 2x 2x 2x 2x 1x 2x 2x | /**
* Chromosome names, reconciled across the conventions that write them.
*
* Two files of the same genome disagree about its names more often than they
* agree. UCSC writes `chr1`, Ensembl writes `1`, a `.hic` off 4DN writes `1`,
* a yeast cooler writes `chrI` and the `chrom.sizes` beside it writes `01`.
* Every one of those is the first chromosome, and until now every one of them
* was a different sequence to this viewer: a companion panel asked for `chr1`
* against a file that calls it `1` got `unknown-label`, and a bigWig of the
* same assembly drew nothing beside a map that had it under another spelling.
*
* So this module answers one question — *does this name, in this file, mean the
* same sequence as that name, in that one* — and it answers it under three
* constraints, which are what the rest of the file is for.
*
* **1. It never silently matches two different sequences.** A wrong match is
* worse than no match: no match is a blank panel and a sentence saying why, and
* a wrong one is somebody else's chromosome drawn under your label, which
* nothing on screen would show. So every step below is a rule with a reason,
* `length` vetoes rather than persuades, and a name whose shape this module does
* not recognise is matched **by its spelling and not otherwise** — case folded,
* with the `chr` prefix off if it had one, and nothing interpreted. That clause
* is the load-bearing one for a metacool: assembler contigs (`NODE_1_length_…`,
* `k141_9`, `tig00000001`) are opaque ids from independently assembled
* organisms and two of them agree by coincidence (§8.5), so no numeral, no
* accession and no organelle table is ever applied to one.
*
* **2. The decisions are made from the whole list, not one name at a time.**
* `X` is the tenth chromosome of *S. cerevisiae* and the sex chromosome of
* everything else, and the string cannot tell you which. The list can: a file
* that also holds `IX` and `XI` is counting in Roman numerals and its `X` is
* ten; a file whose Roman numerals stop at `V` — *C. elegans* is `I`…`V`, `X` —
* is naming a sex chromosome. That is why the entry point is
* {@link NameIndex.of}, over a whole file's sequences, rather than a
* `canonicalise(name)` anybody could call on a string in isolation.
*
* **3. Length corroborates; it never matches.** Two sequences of equal length
* are not the same sequence — a metagenome has thousands of equal-length
* contigs — so no pair is ever matched *because* the lengths agree. The
* implication runs the other way: where a name match is proposed and both
* lengths are known and they differ, the match is reported as such
* ({@link NameMatch.lengths}) so the caller can refuse it, warn about it, or —
* for the navigation lock, which has its own tolerance for a short last bin
* (§16.4) — decide for itself. hg19's `chrM` and hg38's `chrM` are the case
* that matters: same name, different sequence, two bases apart.
*
* ## The ladder
*
* A match carries the {@link MatchTier} that reached it, ordered by how much
* interpretation it took:
*
* | tier | example |
* | --- | --- |
* | `exact` | `chr1` = `chr1` |
* | `case` | `Chr1` = `chr1` |
* | `decorated` | `ref\|NC_001133\|` = `NC_001133` |
* | `prefix` | `chr1` = `1` |
* | `padded` | `01` = `1` |
* | `roman` | `chrXII` = `12` |
* | `organelle` | `chrM` = `MT` = `MtDNA` |
* | `accession` | `NC_000001.11` = `chr1`; `chrUn_GL000220v1` = `GL000220.1` |
* | `version` | `NC_000001.10` ≈ `NC_000001.11` |
*
* `version` is last and is the only tier that is *known* to be shaky: the same
* locus at two assembly versions is two sequences, so it is offered and
* flagged rather than taken.
*
* ## What is deliberately not equated
*
* - **A chromosome arm is not its chromosome.** *Drosophila*'s `2L` and `2R`
* are separate sequences and neither is `2`. The trailing letter stays in the
* key, which also keeps wheat's `1A`, `1B` and `1D` — three homoeologues, one
* number — apart from each other and from `1`.
* - **A linkage group is not a chromosome number.** `LG1` keeps its `LG`,
* because a linkage map is numbered by linkage and an assembly by length, and
* the two orders agree only by luck.
* - **`_random`, `_alt`, `_fix` and `_hapN` stay.** A patch is a different
* sequence from the chromosome it patches.
* - **Genome and MAG names.** This module is about sequences. A metacool's
* genome layer is a list of independently assembled organisms and nothing
* about their names is a convention.
*/
/** One sequence, as any file reports one. `length` where the file knows it. */
export interface NamedSequence {
name: string
length?: number
/**
* The genome this sequence belongs to, on a file that has a genome layer.
*
* Carried for the overlap report and nothing else (§8.5): the matcher itself
* has no use for it — a metagenome's contig names are opaque ids and are
* matched by spelling alone, which is what makes the rename safe here at all
* — but the *report* on a metagenome is about MAGs rather than about
* sequences, and this is where the two tables meet.
*/
genome?: string
}
/**
* How a match was reached, weakest interpretation first.
*
* Ordered, and the order is used: {@link NameIndex.find} takes the strongest
* available match, and where two of this file's names answer to one foreign
* name the tier is what breaks the tie.
*/
export const MATCH_TIERS = [
'exact',
'case',
'decorated',
'prefix',
'padded',
'roman',
'organelle',
'accession',
'version',
] as const
export type MatchTier = (typeof MATCH_TIERS)[number]
/** Whether the two sequences' lengths back the match up, where both are known. */
export type LengthVerdict = 'agree' | 'differ' | 'unknown'
/** One name, resolved against one file's list of sequences. */
export interface NameMatch {
/** The name **as this file writes it** — what to hand a reader or a range. */
name: string
/** The name that was asked for, kept so a report can print both. */
asked: string
tier: MatchTier
lengths: LengthVerdict
}
/**
* The naming convention a whole list is written in.
*
* Reported rather than acted on — the matching below is per name and needs no
* style — because it is the one sentence that makes a mismatch legible in the
* info panel: *this file is UCSC, that one is Ensembl*.
*/
export type NameStyle =
| 'ucsc'
| 'ensembl'
| 'roman'
| 'accession'
| 'assembly'
| 'mixed'
| 'empty'
// ---------------------------------------------------------------------------
// Decoration, prefixes and roles
// ---------------------------------------------------------------------------
/**
* Database tags that appear in a pipe-delimited FASTA header and carry no
* identity of their own.
*
* `gi|568336023|gb|CM000663.2|` is one sequence written by an NCBI tool of a
* certain vintage, and the only part of it worth keeping is `CM000663.2`.
*/
const DB_TAGS = new Set([
'gi',
'gb',
'ref',
'emb',
'dbj',
'tpg',
'tpe',
'tpd',
'lcl',
'pir',
'prf',
'sp',
'tr',
'pdb',
'ena',
'bbs',
])
// **`gnl` is deliberately absent**, and it is the one anybody would add. NCBI's
// `gnl|db|id` names a sequence by *both* remaining fields, so reducing it to
// the last one throws the database away — and `gnl|MAG_042|NODE_1` and
// `gnl|MAG_007|NODE_1` would then both become `NODE_1`, which is two organisms'
// first contigs collided at tier `exact`. Left unrecognised, the whole string is
// the name, which is what it is.
/**
* Strip a name down to the token that identifies it.
*
* Three things come off, in this order, and each is a real thing found in real
* files:
*
* - **everything after the first whitespace**, which is a FASTA description
* (`>chr1 AC:CM000663.2 LN:248956422`) and never part of the name — this is
* also what `samtools` and every reader of a `.fai` do;
* - **pipe decoration**, reduced to the last token that is not a database tag
* and not the bare numeric id that follows `gi`;
* - **a trailing comma or semicolon**, which is a `chrom.sizes` written by a
* spreadsheet.
*/
export function stripDecoration(raw: string): string {
let text = raw.trim().split(/\s+/)[0] ?? ''
text = text.replace(/[,;]+$/, '')
if (text.includes('|')) {
const parts = text.split('|').filter((part) => part !== '')
// **Only where a database tag says so.** A pipe is a legal character in a
// contig name and binners use it: `MAG_042|NODE_1` and `MAG_007|NODE_1` are
// two organisms' first contigs, and reducing both to `NODE_1` would collide
// them at tier `exact` — the loudest possible version of the one thing this
// module promises never to do. A header this reduces has to *look* like
// NCBI's, which means carrying one of NCBI's tags.
if (parts.some((part) => DB_TAGS.has(part.toLowerCase()))) {
const useful = parts.filter((part, at) => {
if (DB_TAGS.has(part.toLowerCase())) return false
// The number in `gi|568336023|…` is an identifier of the *record*, not
// of the sequence, and it is the one all-digit token that must not
// survive.
return !(/^[0-9]+$/.test(part) && at > 0 && parts[at - 1].toLowerCase() === 'gi')
})
if (useful.length > 0) text = useful[useful.length - 1]
}
}
return text
}
/**
* Prefixes that say "this is a chromosome" and nothing else.
*
* `chr` is UCSC's; `chrom` and `chromosome` are what a hand-written
* `chrom.sizes` and several assembly-report converters produce. Each may be
* followed by one separator. Longest first, so `chromosome_1` does not lose
* only its `chr` and keep `omosome_1`.
*/
const CHROM_PREFIX = /^(?:chromosome|chrom|chr)[ _.-]?/i
/**
* Take the chromosome prefix off, or `null` where taking it off would be wrong.
*
* The prefix cannot be stripped on sight, and the names that prove it are
* ordinary ones from an ordinary metagenome: `Christensenella_1` begins with
* `Chr`, and `Chromobacterium_ctg1` begins with `Chrom`. Stripped blindly they
* become `istensenella_1` and `obacterium_ctg1` — two names no file contains,
* which would then match each other's mangling rather than themselves.
*
* So the prefix comes off only when what is left **reads as a chromosome**:
* a number, a Roman numeral, a sex letter, an organelle, an accession, UCSC's
* `Un_…`, or a short letter run in front of a number (`LG1`). Everything else
* keeps its name whole, which is also what a bacterial replicon genuinely
* called `Chromosome` needs.
*/
function unprefixed(bare: string): string | null {
const rest = bare.replace(CHROM_PREFIX, '')
if (rest === '' || rest === bare) return null
const lower = rest.toLowerCase()
if (/^[0-9]/.test(rest)) return rest
if (SEX_LETTERS.has(lower)) return rest
if (ORGANELLE_OF.has(lower)) return rest
if (romanValue(rest) > 0) return rest
if (/^un[_.-]/i.test(rest)) return rest
if (/^[A-Za-z]{1,2}[0-9]/.test(rest)) return rest
if (REFSEQ_ACCESSION.test(rest) || INSDC_ACCESSION.test(rest.replace(/\.[0-9]+$/, ''))) {
return rest
}
return null
}
/**
* The linkage-group prefix, which is a prefix and **not** a chromosome one.
*
* `LG1` and `LG01` are one sequence and want the same padding rule every other
* number gets. `LG1` and `1` are not, and must not be: a linkage map is
* numbered by linkage and an assembly by length, and the two orders agree only
* by luck. So the prefix is recognised — enough to fold `LG1`, `LG_01` and
* `lg1` together — and then kept in the key, in a namespace of its own.
*/
const GROUP_PREFIX = /^(?:lg|linkage_?group|group)[ _.-]?(?=[0-9])/i
/**
* Suffixes that make a sequence a *different* sequence from the one it is
* named after, and therefore stay in the key.
*
* `chr1_KI270706v1_random` is an unplaced fragment believed to belong to
* chromosome 1; `chr6_GL000250v2_alt` is one of the MHC haplotypes. Neither is
* chromosome 1 or 6, and equating them would draw a 175 kb scaffold under the
* label of a 249 Mb chromosome.
*/
const ROLE_SUFFIX = /_(random|alt|fix|hap\d+|maternal|paternal)$/i
/**
* An INSDC accession as UCSC rewrites it into a name: `GL000220v1`.
*
* Bounded by a separator or an end rather than by `\b`, which does not exist
* between `_` and `G` — `_` is a word character, so a word boundary never fires
* inside `chrUn_GL000220v1`, which is the only place this pattern is ever
* looked for.
*
* **Upper case only, and that is deliberate.** The `.1` → `v1` rewrite belongs
* to UCSC's hg38/mm39 generation. The one before it — hg19, mm10 — lowercased
* the accession and *discarded the version*: `GL000220.1` became
* `chrUn_gl000220`, and `GL000195.1` is `chr7_gl000195_random` in hg19 and
* `chrUn_GL000195v1` in hg38, the same sequence under two roles. There is no
* closed-form way back from an hg19 name to an accession, because the version
* digit is simply gone and which version it was depends on the assembly. So the
* old generation is not recognised at all rather than guessed at: an
* unrecognised name matches by its spelling and finds nothing, which is a blank
* lane and a sentence, where a guess would be a scaffold drawn under the label
* of a different one.
*/
const UCSC_ACCESSION = /(?:^|[_.-])([A-Z]{2}[0-9]{5,6})v([0-9]+)(?:$|[_.-])/
/** RefSeq (`NC_000001`), INSDC (`CM000663`, `U00096`) and WGS master accessions. */
const REFSEQ_ACCESSION = /^(N[CGTWZ]|AC)_([0-9]{5,})$/i
/**
* INSDC accessions, and the case sensitivity is the point.
*
* Accessions are upper case, always, and requiring that is what keeps an
* assembler's `contig00001` — six letters and five digits, the same shape — out
* of the accession namespace and safely opaque.
*/
const INSDC_ACCESSION = /^[A-Z]{1,6}[0-9]{5,8}$/
// ---------------------------------------------------------------------------
// Organelles, plasmids and sex chromosomes
// ---------------------------------------------------------------------------
/**
* The organelle spellings worth knowing, and the reason there is a table at
* all.
*
* Everything else in this module is a *rule* — strip a prefix, read a numeral,
* drop a version. The organelles are the one place where the names are
* genuinely arbitrary and no rule relates them: nothing derives `MtDNA` from
* `chrM`, or `dmel_mitochondrion_genome` from `MT`. The table is small and
* closed on purpose; it is spellings of three things, not a genome database.
*
* The four accessions are the reference organelle sequences a pipeline is
* likeliest to have written instead of a name: the human rCRS, its GenBank
* twin, the *S. cerevisiae* mitochondrion and the *A. thaliana* plastid.
*
* The spellings are matched **whole**, never by prefix, and *S. pombe* is why:
* its `MTR` is the mating-type region, twenty kilobases that have nothing to do
* with a mitochondrion, and a prefix test on `MT` would swallow it.
*
* Two mitochondria in one file is a real state, not a corruption, and this
* table does not try to resolve it: UCSC's hg19 analysis set carries the legacy
* `chrM` (16,571 bp) beside `chrMT` (the rCRS, 16,569) precisely so that reads
* can be remapped without breaking legacy coordinates. Both land in this
* bucket, which makes the bucket ambiguous, which makes {@link NameIndex.find}
* refuse to guess unless a length settles it — the right answer, arrived at by
* the general rule rather than by a special case.
*/
const ORGANELLES: Array<[key: string, spellings: string[]]> = [
[
'mito',
[
'm',
'mt',
'mtdna',
'mito',
'mitochondrion',
'mitochondria',
'mitochondrial',
'mitochondrion_genome',
'dmel_mitochondrion_genome',
'mitochondrial_genome',
'mitochondrion_dna',
'chrmt',
'nc_012920',
'j01415',
'nc_001224',
'nc_005089',
],
],
[
'plastid',
[
'c',
'pt',
'cp',
'chloroplast',
'plastid',
'chloroplast_genome',
'chrc',
'nc_000932',
],
],
['2micron', ['2-micron', '2micron', '2u', '2-micron_plasmid', 'nc_001398']],
]
/** Spelling → organelle key, built once. */
const ORGANELLE_OF = new Map<string, string>()
for (const [key, spellings] of ORGANELLES) {
for (const spelling of spellings) ORGANELLE_OF.set(spelling, key)
}
/** The sex-chromosome letters, including the ZW system birds and moths use. */
const SEX_LETTERS = new Set(['x', 'y', 'z', 'w'])
// ---------------------------------------------------------------------------
// Roman numerals
// ---------------------------------------------------------------------------
/**
* Roman numerals as chromosome names go — `I` to `XLVIII`, and no further.
*
* **`C`, `D` and `M` are excluded from the numeral system entirely**, which is
* the whole reason this is a hand-rolled regex rather than a general Roman
* parser. No genome has a hundredth chromosome, so a `C` in a chromosome list
* is a chloroplast and an `M` is a mitochondrion — every time, in every file
* this viewer will ever be shown. Reading them as 100 and 1000 would be
* arithmetically correct and biologically absurd, and it would make `chrM` and
* `chrMT` two different sequences.
*/
const ROMAN = /^(XL|L|X{0,3})(IX|IV|V?I{0,3})$/i
const ROMAN_TENS: Record<string, number> = { '': 0, x: 10, xx: 20, xxx: 30, xl: 40, l: 50 }
const ROMAN_UNITS: Record<string, number> = {
'': 0,
i: 1,
ii: 2,
iii: 3,
iv: 4,
v: 5,
vi: 6,
vii: 7,
viii: 8,
ix: 9,
}
/** The value of a chromosome-shaped Roman numeral, or `0` for anything else. */
export function romanValue(text: string): number {
const match = ROMAN.exec(text)
if (match === null) return 0
const tens = ROMAN_TENS[match[1].toLowerCase()]
const units = ROMAN_UNITS[match[2].toLowerCase()]
if (tens === undefined || units === undefined) return 0
return tens + units
}
// ---------------------------------------------------------------------------
// Accession tables
// ---------------------------------------------------------------------------
/**
* RefSeq's chromosome accessions for the two assemblies that account for most
* of the world's Hi-C, and the only per-species knowledge in this file.
*
* They are a range and not a list: NCBI assigned human chromosomes 1–22, X and
* Y the consecutive block `NC_000001`–`NC_000024`, and mouse 1–19, X and Y the
* block `NC_000067`–`NC_000087`. Both are stable across assembly versions —
* only the `.N` suffix moves — so a file naming its sequences `NC_000001.11`
* lines up with one naming them `chr1` by arithmetic rather than by table.
*
* Nothing else is hard-coded, and this is where the line is: two ranges buy the
* overwhelming majority of accession-named files, and a real alias table for
* every assembly is megabytes, needs a network, and would have to be told which
* assembly a file is of — which is the question this module exists to avoid
* asking.
*/
const REFSEQ_RANGES: Array<{ from: number; to: number; first: number; tail: string[] }> = [
// Human: NC_000001–NC_000022 are 1–22, then X, then Y.
{ from: 1, to: 22, first: 1, tail: ['x', 'y'] },
// Mouse: NC_000067–NC_000085 are 1–19, then X, then Y.
{ from: 67, to: 85, first: 1, tail: ['x', 'y'] },
]
/**
* The chromosome an `NC_` accession names, as a canonical body, or `null`.
*
* `NC_000001` → `1`; `NC_000023` → `x`; `NC_000086` → `x` (mouse). Deliberately
* one-way: `1` is not turned into an accession, because which accession depends
* on the species and that is exactly what is not known here.
*/
function refseqChromosome(digits: number): string | null {
for (const range of REFSEQ_RANGES) {
if (digits >= range.from && digits <= range.to) {
return String(range.first + (digits - range.from))
}
const after = digits - range.to - 1
if (after >= 0 && after < range.tail.length) return range.tail[after]
}
return null
}
// ---------------------------------------------------------------------------
// Canonical form
// ---------------------------------------------------------------------------
/** What a name was reduced to, and what it cost to get there. */
interface Canon {
/**
* The key two names must share to be the same sequence.
*
* Namespaced by kind — `num:12`, `sex:x`, `org:mito`, `acc:nc_000001`,
* `raw:node_1` — so that a chromosome numbered 12 and a contig literally
* called `num:12` cannot collide, and so that an opaque name can never key
* into the same bucket as an interpreted one.
*/
key: string
/** The interpretations applied, for reporting which tier a match used. */
via: MatchTier[]
/** The accession's version, where the key dropped one. */
version: string | null
/** `true` when nothing about this name was interpreted — exact match only. */
opaque: boolean
}
/**
* The assembly-wide decisions a list makes on behalf of its own names.
*
* Carried rather than recomputed because it belongs to the list a name came
* *from*, not to the one it is being looked up in: `X` out of a yeast file is
* chromosome ten however the file it is being matched against numbers its own.
*/
export interface NameContext {
/** `true` where `X` in this list is the tenth chromosome rather than the sex one. */
xIsTen: boolean
/** `true` where this list counts in Roman numerals at all. */
roman: boolean
/**
* `true` where a bare number in this list is a chromosome's *ordinal* rather
* than an assembler's *id*.
*
* The one thing that separates a karyotype from a draft assembly, and it is
* not the names — SOAPdenovo, ABySS, Shasta and several binners all emit
* contigs called `1`, `2`, `3`. Nothing about the string `1` says which it is,
* and read as an ordinal it matches `chr1` at the same rung an Ensembl file
* does, which would draw a 4 kb contig under the label of chromosome one.
*
* What separates them is *how many there are*: no genome has two hundred
* chromosomes, and every draft assembly has thousands of contigs. See
* {@link MAX_KARYOTYPE}.
*/
ordinals: boolean
}
/**
* More numbered sequences than this and the numbers are ids, not chromosomes.
*
* Deliberately generous. The largest karyotypes anybody assembles are around a
* hundred and twenty, so two hundred leaves every real genome room and still
* separates it by an order of magnitude from the draft assemblies this is here
* to keep out. The cost of being wrong in each direction is not symmetric: too
* high and a metagenome's `1` starts answering to `chr1`, too low and a
* hypothetical two-hundred-chromosome genome loses cross-convention matching
* and keeps exact matching, which is where it was before this module existed.
*/
const MAX_KARYOTYPE = 200
/**
* Unambiguous Roman numerals — the ones that cannot be read as anything else.
*
* `I`, `V` and `X` are all three of a numeral, a letter and (for `X`) a sex
* chromosome, so none of them is evidence of anything. `II`, `IV`, `IX`, `XII`
* are evidence, and two of them settle it.
*/
function readsAsRoman(body: string): boolean {
if (body.length < 2) return false
if (SEX_LETTERS.has(body.toLowerCase())) return false
return romanValue(body) > 0
}
/**
* What a whole list decides about its own numerals, before any name is read.
*
* **The Roman question** is settled by two or more unambiguous numerals: one
* `II` could be a contig, but `II` and `IV` together in a list of sixteen names
* is *S. cerevisiae*.
*
* **The `X` question** is settled by its Roman neighbours, and this is the
* sharpest rule in the module. A list holding `IX` or `XI` is counting past
* nine in Roman, so its `X` is ten — sixteen yeast chromosomes, `I` to `XVI`.
* A list whose numerals stop at `V` and then jumps to `X` is *C. elegans*:
* `I`, `II`, `III`, `IV`, `V`, `X`, five autosomes and a sex chromosome, and
* there is no chromosome ten to be confused with. The same test gets
* *S. pombe* right (`I`, `II`, `III` and no `X` at all) and gets every numeric
* assembly right by never reaching the question.
*
* With one exception, and it is a real file rather than a hypothetical: a Hi-C
* library mapped against a **host plus a yeast spike-in** has one contig list
* holding `chr1`…`chr22`, `chrX`, `chrY` *and* `chrI`…`chrXVI`. The Roman
* evidence is overwhelming and the conclusion would be that this file's `chrX`
* is chromosome ten — which is the host's sex chromosome, re-keyed onto the
* spike-in's tenth. So a list that numbers chromosomes **both** ways does not
* get to answer the `X` question at all: in a list that already counts in
* Arabic, `X` is the sex chromosome, which is what it is in every genome that
* has both notations in it.
*/
export function contextOf(names: readonly string[]): NameContext {
const bodies = names.map((name) => bodyOf(name))
const evidence = bodies.filter((body) => readsAsRoman(body))
const roman = evidence.length >= 2
// Counted by *plausible ordinal*, not by "is all digits", and the difference
// is a real assembly rather than a hypothetical one: Ensembl's *Drosophila*
// carries hundreds of scaffolds named `211000022278279`, and counting those
// would push the file past the ceiling and take `2L`, `2R` and `4` down with
// them. A fifteen-digit number is not a chromosome ordinal under any
// convention, so it never was evidence about this list either way.
const numbers = bodies.filter(
(body) => /^[0-9]+$/.test(body) && Number(body) >= 1 && Number(body) <= MAX_KARYOTYPE,
)
const ordinals = numbers.length < MAX_KARYOTYPE
const has = (want: string): boolean => bodies.some((body) => body.toLowerCase() === want)
// Two, not one: a single `4` beside sixteen Roman numerals is a stray contig,
// and `I`…`XVI` plus `chr2micron` must not lose its X to it.
const alsoArabic = ordinals && numbers.length >= 2
return { roman, ordinals, xIsTen: roman && !alsoArabic && (has('ix') || has('xi')) }
}
/** A name stripped of decoration, chromosome prefix and role suffix. */
function bodyOf(name: string): string {
const bare = stripDecoration(name)
return (unprefixed(bare) ?? bare).replace(ROLE_SUFFIX, '')
}
/**
* Reduce one name to the key that decides what it is.
*
* The order of the tests is the order of confidence, and each one that fires
* ends the reduction. What falls through every test is opaque, keyed under its
* own lowercased text, and can from then on only match something spelled the
* same way — which is the guarantee the module header opens with.
*/
export function canonicalise(name: string, context: NameContext): Canon {
const via: MatchTier[] = []
const bare = stripDecoration(name)
if (bare !== name.trim()) via.push('decorated')
const stripped = unprefixed(bare)
const withRole = stripped ?? bare
if (stripped !== null) via.push('prefix')
const role = ROLE_SUFFIX.exec(withRole)
const body = role === null ? withRole : withRole.slice(0, role.index)
const tail = role === null ? '' : `+${role[1].toLowerCase()}`
const lower = body.toLowerCase()
// An accession UCSC has rewritten into a name — `chrUn_GL000220v1`,
// `chr22_KI270733v1_random`. The accession is the identity; the chromosome
// the name hangs it off and the role suffix are both commentary, and Ensembl
// writes the same sequence as `GL000220.1` with neither.
const rewritten = UCSC_ACCESSION.exec(withRole)
if (rewritten !== null) {
via.push('accession')
return {
key: `acc:${rewritten[1].toLowerCase()}`,
via,
version: rewritten[2],
opaque: false,
}
}
// The version comes off before anything else is recognised, because every
// test below is about the accession and none of them is about which assembly
// it came from. Kept, not discarded: two versions of one accession are the
// same locus in two assemblies, which is a match worth offering and never
// worth taking silently.
const versioned = /^(.*?)\.([0-9]+)$/.exec(body)
const unversioned = versioned === null ? body : versioned[1]
const version = versioned === null ? null : versioned[2]
// Organelles **first**, and this order is load-bearing: the reference
// mitochondrial and plastid sequences are accessions (`NC_012920.1` is the
// human rCRS) and the accession branch below would key them by their number
// rather than as what they are, leaving `chrM` and `NC_012920.1` two
// different sequences in the one case a table exists to prevent.
const organelle = ORGANELLE_OF.get(lower) ?? ORGANELLE_OF.get(unversioned.toLowerCase())
if (organelle !== undefined) {
if (organelle !== lower) via.push('organelle')
return { key: `org:${organelle}`, via, version, opaque: false }
}
const refseq = REFSEQ_ACCESSION.exec(unversioned)
if (refseq !== null) {
via.push('accession')
// **`NC_` only.** The prefixes share one digit space and mean different
// things: `NC_000001` is human chromosome one and `NW_000001` is a scaffold
// that happens to have been allocated the same number. Reading the digits
// without the prefix turns every `NW_`, `NT_`, `NZ_` and `NG_` in the
// human and mouse ranges into a chromosome.
const chromosome =
refseq[1].toLowerCase() === 'nc' ? refseqChromosome(Number(refseq[2])) : null
// A RefSeq accession this module can name is keyed as the chromosome, so
// `NC_000001.11` and `chr1` land in one bucket. One it cannot is still an
// accession, and two files writing the same one still meet.
if (chromosome !== null) {
return {
key: SEX_LETTERS.has(chromosome) ? `sex:${chromosome}${tail}` : `num:${chromosome}${tail}`,
via,
version,
opaque: false,
}
}
return { key: `acc:${unversioned.toLowerCase()}${tail}`, via, version, opaque: false }
}
if (INSDC_ACCESSION.test(unversioned)) {
via.push('accession')
return { key: `acc:${unversioned.toLowerCase()}${tail}`, via, version, opaque: false }
}
// A plain number, with its leading zeros gone. `01`, `1` and `chr1` are one
// chromosome in every file that writes any of them — *provided* this list is
// a karyotype and not a draft assembly, which is the one thing the string
// cannot say and the list can. See {@link NameContext.ordinals}.
// The ceiling is per name as well as per list: a sequence called
// `211000022278279` is an Ensembl scaffold id, not the two-hundred-trillionth
// chromosome, and keying it as an ordinal would put an id in the karyotype
// namespace one name at a time rather than a whole list at a time.
if (/^[0-9]+$/.test(body) && context.ordinals && Number(body) <= MAX_KARYOTYPE) {
if (/^0[0-9]/.test(body)) via.push('padded')
return { key: `num:${Number(body)}${tail}`, via, version: null, opaque: false }
}
// A number with a letter welded to it: a *Drosophila* arm (`2L`), a wheat
// homoeologue (`1A`), a rice pseudomolecule (`01g`). The letter stays. See
// the module header — an arm is not its chromosome.
//
// **At most two digits**, and that bound is doing real work: FALCON names its
// contigs `000001F` and `000123F`, which is this pattern exactly, and reading
// one as chromosome 1 arm F would put an assembler's contig into the
// karyotype namespace — the one thing this module promises never to do. No
// chromosome is numbered past two digits, so nothing real is lost.
const armed = /^([0-9]{1,2})([a-z]{1,2})$/i.exec(body)
if (armed !== null && context.ordinals) {
if (armed[1].startsWith('0')) via.push('padded')
return {
key: `num:${Number(armed[1])}${armed[2].toLowerCase()}${tail}`,
via,
version: null,
opaque: false,
}
}
// A linkage group, folded on its number and kept out of the chromosomes'
// namespace. See {@link GROUP_PREFIX}.
const group = GROUP_PREFIX.exec(body)
if (group !== null) {
const digits = body.slice(group[0].length)
if (/^[0-9]+$/.test(digits)) {
if (/^0[0-9]/.test(digits)) via.push('padded')
return { key: `lg:${Number(digits)}${tail}`, via, version: null, opaque: false }
}
}
// The sex chromosomes, and the one place the whole list has already voted.
if (SEX_LETTERS.has(lower) && !(lower === 'x' && context.xIsTen)) {
return { key: `sex:${lower}${tail}`, via, version: null, opaque: false }
}
if (context.roman) {
const value = romanValue(body)
if (value > 0) {
via.push('roman')
return { key: `num:${value}${tail}`, via, version: null, opaque: false }
}
}
// Everything else: an assembler's contig, a linkage group, a scaffold, a
// plasmid nobody has named twice the same way. Case-folded and no more.
return { key: `raw:${lower}${tail}`, via, version: null, opaque: true }
}
// ---------------------------------------------------------------------------
// One file's names, ready to be asked questions
// ---------------------------------------------------------------------------
/** Where a tier sits on the ladder; higher is more interpretation. */
function tierRank(tier: MatchTier): number {
return MATCH_TIERS.indexOf(tier)
}
/**
* The tier to report for a match between two canonical forms.
*
* The *most interpreted* step either side took to get to the shared key, which
* is the honest thing to print: `chrI` against `1` is a `roman` match even
* though the prefix came off first, because the numeral is the part a reader
* would want to check.
*/
function tierOf(a: Canon, b: Canon): MatchTier {
let best: MatchTier = 'case'
for (const tier of [...a.via, ...b.via]) {
if (tierRank(tier) > tierRank(best)) best = tier
}
return best
}
/** Whether two lengths are close enough to call the same sequence. */
function lengthsVerdict(a: number | undefined, b: number | undefined): LengthVerdict {
if (a === undefined || b === undefined || a <= 0 || b <= 0) return 'unknown'
return a === b ? 'agree' : 'differ'
}
/** {@link NameIndex.for}'s memo, keyed on the list's own identity. */
const INDEX_CACHE = new WeakMap<object, NameIndex>()
/**
* One file's sequences, indexed every way a foreign name might arrive.
*
* Built once per file and held for as long as the file is open: it is three
* `Map`s over the contig table, which for the 154 k-contig metacool that sets
* every other budget in this viewer is a few megabytes of strings that were
* already in memory, and the alternative — canonicalising the whole list per
* lookup — is a linear scan on every navigation.
*/
export class NameIndex {
/** The file's names, in file order. */
readonly names: readonly string[]
/** What this file decided about its own numerals — see {@link NameContext}. */
readonly context: NameContext
private styleCache: NameStyle | null = null
/**
* The convention this list is written in — computed on first ask.
*
* Lazy because it is a *reporting* field: the info panel prints it and
* nothing else consults it, while every index built to answer a navigation
* would otherwise pay for a second full pass over the contig table to
* canonicalise every name again.
*/
get style(): NameStyle {
this.styleCache ??= styleOf(this.names, this.context)
return this.styleCache
}
private readonly exact = new Map<string, NamedSequence>()
private readonly folded = new Map<string, NamedSequence[]>()
private readonly keyed = new Map<string, Array<{ sequence: NamedSequence; canon: Canon }>>()
private constructor(sequences: readonly NamedSequence[]) {
this.names = sequences.map((sequence) => sequence.name)
this.context = contextOf(this.names)
for (const sequence of sequences) {
// First writer wins throughout. A file with two sequences of one name is
// corrupt (`parseChromSizes` says so for a `chrom.sizes`), and the first
// is the one every other index in this app resolves to.
if (!this.exact.has(sequence.name)) this.exact.set(sequence.name, sequence)
push(this.folded, sequence.name.toLowerCase(), sequence)
const canon = canonicalise(sequence.name, this.context)
push(this.keyed, canon.key, { sequence, canon })
}
}
static of(sequences: readonly NamedSequence[]): NameIndex {
return new NameIndex(sequences)
}
/** Build from names alone — a tabix index, a BED, a bigWig header. */
static ofNames(names: readonly string[]): NameIndex {
return new NameIndex(names.map((name) => ({ name })))
}
/**
* The index for a list, built once per list.
*
* Held against the **array's own identity**, which is what makes this safe to
* call from a render path: the assembly's contigs, a reader's `chromnames`
* and the map's name column are each one array that outlives every question
* anybody asks of it, so the second caller and the ten-thousandth get the
* first one's index.
*
* It is not decoration. `findContig` is called on every keystroke in the
* locus box, and a keystroke mid-word is a *miss* — which is the path that
* reaches the index rather than short-circuiting on an exact name. Building
* one per press costs 24 ms at five thousand sequences and 770 ms at a
* hundred and fifty thousand, which is a locus box that stops taking input.
*
* The one rule: **the array must not be mutated afterwards.** Nothing here
* does — the two places that rewrite a contig list in place
* (`annotations.worker.ts`) build no index from it — and a list that changed
* under a cached index would answer with names it no longer has.
*/
static for(list: readonly string[] | readonly NamedSequence[]): NameIndex {
const held = INDEX_CACHE.get(list)
if (held !== undefined) return held
const built =
typeof list[0] === 'string'
? NameIndex.ofNames(list as readonly string[])
: NameIndex.of(list as readonly NamedSequence[])
INDEX_CACHE.set(list, built)
return built
}
/** `true` when this file writes this exact name. */
has(name: string): boolean {
return this.exact.has(name)
}
/**
* The name **this file** uses for a sequence another file calls `name`.
*
* The ladder in order: the same string, then the same string in another case,
* then the canonical key. `length`, where the caller knows it, never finds a
* match and only ever judges one — see the module header.
*
* `from` is the context of the list the name **came out of**, and passing it
* is what makes an asymmetric pair work: `chrI` is chromosome one because the
* file it came from counts in Roman numerals, and the file being searched —
* which may number its own sequences `01` to `16` — has no way to know that.
* Omitted, this file's own context stands in, which is the right reading for
* a name somebody typed into the locus box.
*
* `null` where nothing answers, and where more than one thing answers
* *ambiguously*: a file holding both `1` and `01` cannot say which one a
* foreign `chr1` meant, and guessing would be the silent wrong match this
* module exists to refuse.
*/
find(name: string, options: { length?: number; from?: NameContext } = {}): NameMatch | null {
const { length } = options
const direct = this.exact.get(name)
if (direct !== undefined) {
return {
name: direct.name,
asked: name,
tier: 'exact',
lengths: lengthsVerdict(length, direct.length),
}
}
const folded = this.folded.get(name.toLowerCase())
if (folded !== undefined && folded.length === 1) {
return {
name: folded[0].name,
asked: name,
tier: 'case',
lengths: lengthsVerdict(length, folded[0].length),
}
}
const context = options.from ?? this.context
const found = this.byKey(name, canonicalise(name, context), length)
if (found !== null) return found
// The numeral nobody declared. A name arrives with no context of its own —
// typed into the locus box, or read off a BED that carries no list — and
// `XII` is then a numeral this file has no reason to expect. It is also a
// numeral that cannot be anything else, so it is tried a second time under
// a Roman reading.
//
// **`X` is excluded, and that exclusion is the whole safety of this
// retry.** `X` unqualified is the sex chromosome far more often than it is
// ten, and the only thing that can say otherwise is the list it came from —
// which is precisely what this path does not have. `L` goes with it: a
// fiftieth chromosome is not a thing, so a bare `L` is a name.
//
// What that leaves reaching this line as a *single letter* is `I` and `V`
// and nothing else — `M` and `C` were taken by the organelles long before
// here, and `D` is not a numeral in this module at all. Both are allowed on
// purpose: a sequence called `I` that is not the first chromosome, or `V`
// that is not the fifth, is not a file anybody has. This is deliberately
// more permissive than {@link readsAsRoman}, which rejects every single
// letter — but that function is *voting on what a list is*, where one
// ambiguous letter must not decide anything, and this one is resolving a
// name that has already failed every stricter test.
if (!context.roman) {
const body = bodyOf(name).toLowerCase()
if (body !== 'x' && body !== 'l' && romanValue(body) > 0) {
return this.byKey(name, canonicalise(name, { ...context, roman: true, xIsTen: false }), length)
}
}
return null
}
/** The canonical-key rung of {@link find}'s ladder. */
private byKey(asked: string, canon: Canon, length?: number): NameMatch | null {
// Every key is namespaced by kind, so an opaque name can only ever reach a
// bucket of other opaque names — which is what makes "a name this module
// does not recognise matches by its spelling, and not otherwise" true by
// construction rather than by a guard that could be forgotten.
const candidates = this.keyed.get(canon.key)
if (candidates === undefined || candidates.length === 0) return null
const chosen = pick(candidates, length)
if (chosen === null) return null
const tier = tierOf(canon, chosen.canon)
const drifted =
canon.version !== null &&
chosen.canon.version !== null &&
canon.version !== chosen.canon.version
return {
name: chosen.sequence.name,
asked,
tier: drifted && tierRank(tier) < tierRank('version') ? 'version' : tier,
lengths: lengthsVerdict(length, chosen.sequence.length),
}
}
}
/**
* Which of several sequences sharing a key a foreign name meant, or `null`.
*
* One candidate is the answer. More than one is a file that spells the same
* chromosome two ways — `1` and `01` side by side — and the only thing that can
* break the tie honestly is the length, because it is the only evidence that
* comes from the sequence rather than from its spelling. Without a length, or
* with two candidates of the same length, the answer is that there is no
* answer.
*/
function pick<T extends { sequence: NamedSequence }>(candidates: T[], length?: number): T | null {
if (candidates.length === 1) return candidates[0]
if (length === undefined || length <= 0) return null
const agreeing = candidates.filter((entry) => entry.sequence.length === length)
return agreeing.length === 1 ? agreeing[0] : null
}
function push<K, V>(map: Map<K, V[]>, key: K, value: V): void {
const held = map.get(key)
if (held === undefined) map.set(key, [value])
else held.push(value)
}
/**
* What convention a list is written in, for the one sentence an info panel
* shows.
*
* Reported and never acted on. The tests are over the *whole* list and are
* deliberately coarse: a handful of names decide, because a real assembly is a
* couple of dozen chromosomes and several hundred unplaced scaffolds and it is
* the chromosomes that carry the convention.
*/
export function styleOf(names: readonly string[], context = contextOf(names)): NameStyle {
if (names.length === 0) return 'empty'
let prefixed = 0
let bare = 0
let accession = 0
let opaque = 0
for (const name of names) {
const canon = canonicalise(name, context)
if (canon.opaque) {
opaque++
continue
}
// By what the name *is*, not by what it was keyed as: a RefSeq accession
// this module can name resolves to `num:1`, and counting it as a bare
// Ensembl-style number would report a file of accessions as an Ensembl one.
if (canon.via.includes('accession')) accession++
else if (CHROM_PREFIX.test(stripDecoration(name))) prefixed++
else bare++
}
const named = prefixed + bare + accession
if (named === 0 || opaque > named * 4) return 'assembly'
if (context.roman && prefixed <= bare) return 'roman'
if (accession > prefixed && accession > bare) return 'accession'
if (prefixed > 0 && bare > 0) return 'mixed'
if (prefixed > 0) return context.roman ? 'roman' : 'ucsc'
return context.roman ? 'roman' : 'ensembl'
}
// ---------------------------------------------------------------------------
// Two files at once
// ---------------------------------------------------------------------------
/** What matching one file's sequences onto another's produced. */
export interface Alignment {
/** Source name → the target's name for it. Only sequences that matched. */
pairs: Map<string, NameMatch>
/** Source names nothing in the target answered to. */
unmatched: string[]
/** Matches whose two lengths are known and disagree. */
contested: NameMatch[]
/** How many pairs needed more than an exact string match. */
renamed: number
}
/**
* Match every sequence of one file onto another file's list.
*
* **One to one, by construction.** A target sequence is claimed by at most one
* source name, and the claim goes to the strongest tier — so a file holding
* both `1` and `chr1` gives each of them to its own counterpart rather than
* letting the second one overwrite the first. Two source names left fighting
* over one target at the same tier is exactly the ambiguity {@link
* NameIndex.find} refuses, and both lose.
*
* This is what the info panel reports and what {@link compareRefusal} asks
* before refusing two files for having different chromosome lists (§16.4).
*/
export function alignNames(
from: readonly NamedSequence[],
to: readonly NamedSequence[],
): Alignment {
const index = NameIndex.of(to)
// The source list gets an index of its own for one field of it: the context.
// See {@link NameIndex.find} — a Roman numeral is Roman because of the list it
// came out of, and this is the only place both lists are in one hand.
const from_ = NameIndex.of(from).context
const proposals: Array<{ source: NamedSequence; match: NameMatch }> = []
for (const source of from) {
const match = index.find(source.name, { length: source.length, from: from_ })
if (match !== null) proposals.push({ source, match })
}
// Strongest tier first, so the exact matches take their targets before an
// interpreted one can. Ties keep file order, which is what makes this stable.
proposals.sort((a, b) => tierRank(a.match.tier) - tierRank(b.match.tier))
const claimed = new Map<string, { source: string; tier: MatchTier }>()
const contestedTargets = new Set<string>()
for (const proposal of proposals) {
const held = claimed.get(proposal.match.name)
if (held === undefined) {
claimed.set(proposal.match.name, {
source: proposal.source.name,
tier: proposal.match.tier,
})
} else if (held.tier === proposal.match.tier) {
// Two names of the same file, equally entitled to one target. Neither
// wins: this is a genuinely ambiguous list and a guess here is the wrong
// chromosome drawn under the right label.
contestedTargets.add(proposal.match.name)
}
}
const pairs = new Map<string, NameMatch>()
const contested: NameMatch[] = []
let renamed = 0
for (const proposal of proposals) {
const winner = claimed.get(proposal.match.name)
if (winner === undefined || winner.source !== proposal.source.name) continue
if (contestedTargets.has(proposal.match.name)) continue
pairs.set(proposal.source.name, proposal.match)
if (proposal.match.tier !== 'exact') renamed++
if (proposal.match.lengths === 'differ') contested.push(proposal.match)
}
const unmatched = from
.map((sequence) => sequence.name)
.filter((name) => !pairs.has(name))
return { pairs, unmatched, contested, renamed }
}
/** One list of names, rewritten into another list's spelling. */
export interface Renaming {
/** The source list, in its own order, each name replaced where there was one. */
names: string[]
/** Target's spelling → the source's own, for querying the source under it. */
sourceOf: Map<string, string>
/** How many names the rewrite changed. */
renamed: number
/**
* Renames whose two sequences are known to be different lengths.
*
* Carried out rather than suppressed. A track and a map that spell one
* chromosome differently *and* size it differently are probably two assembly
* versions — hg19 against hg38 — and that is a thing to tell a reader, not a
* thing to decide for them: the coordinates still mean something, they just
* do not mean quite the same thing.
*/
contested: NameMatch[]
}
/**
* Put one file's sequence names into another file's vocabulary.
*
* This is how a **track** joins a map, and doing it once at load is what keeps
* the rest of the annotation path unchanged: a bigWig of `chr1` dropped on a
* cooler of `1` has its contig list rewritten to the map's spelling the moment
* it is read, so every lookup after that — the overlap report, the lane's
* window, the feature search, the export — is a lookup by the map's own name
* and has never heard of a convention.
*
* {@link Renaming.sourceOf} is the way back, for the one reader that cannot be
* rewritten: a bigWig is a file on a disk and its `refName`s are whatever it
* says they are, so a query has to be translated on the way out.
*
* Names with no counterpart are **kept as they are**. A track of a different
* assembly is not renamed into agreement with the map, and the overlap report
* that follows still says so — that report is the thing this must not silence
* (§8.2).
*/
export function renameInto(
source: readonly NamedSequence[],
target: readonly NamedSequence[],
): Renaming {
const alignment = alignNames(source, target)
const sourceOf = new Map<string, string>()
const names = source.map((sequence) => {
const match = alignment.pairs.get(sequence.name)
if (match === undefined) return sequence.name
sourceOf.set(match.name, sequence.name)
return match.name
})
// Every source name also answers to **itself**, where nothing has claimed it.
// Without this a reader that can only be queried by `sourceOf` — a bigWig,
// whose refNames are a fact about the file — goes silent the moment there is
// nothing to align against: an empty map contig list, which is what a failed
// contigs read leaves behind, produced an empty translation and a lane that
// drew nothing for the rest of the session. Matches are set first and are not
// overwritten, so an alignment always wins over the identity.
for (const sequence of source) {
if (!sourceOf.has(sequence.name)) sourceOf.set(sequence.name, sequence.name)
}
return { names, sourceOf, renamed: alignment.renamed, contested: alignment.contested }
}
/** {@link NamedSequence}s from a bare list of names, for a source with no lengths. */
export function sequencesOf(names: readonly string[]): NamedSequence[] {
return names.map((name) => ({ name }))
}
/**
* Which of a track's own sequences a caller's name refers to, or `-1`.
*
* The **read** side of §5.9, and it exists because renaming a track once at
* load is not enough on its own. A track is loaded against the session's map
* and renamed into *its* vocabulary — but a deck draws the same track beside
* every panel, and each panel samples through its own block's axis, so a
* companion asks for the sequence by the name **its** file writes. One track,
* three vocabularies, and the rename can only ever have chosen one of them.
*
* So every place a held track is asked for a name goes through here: the
* bigWig's refNames, a bedGraph's contigs, a FASTA's sequences, a computed
* vector's grid, and the feature sets the renderer walks. Exact first — which
* is every lane of the map the track was loaded against, and costs one `Map`
* probe — and the index behind it is held against the list's own identity, so a
* lane redrawing at sixty frames a second builds nothing.
*
* Takes the list a track already has rather than a prepared index, because that
* list is the thing every one of those callers is holding.
*/
export function contigIndexOf(
contigs: readonly string[] | readonly NamedSequence[],
name: string,
): number {
const at = positionsOf(contigs)
const direct = at.get(name)
if (direct !== undefined) return direct
const match = NameIndex.for(contigs).find(name)
return match === null ? -1 : (at.get(match.name) ?? -1)
}
/** Name → position, held against the list's identity beside its index. */
const POSITIONS = new WeakMap<object, Map<string, number>>()
function positionsOf(contigs: readonly string[] | readonly NamedSequence[]): Map<string, number> {
const held = POSITIONS.get(contigs)
if (held !== undefined) return held
const built = new Map<string, number>()
contigs.forEach((contig, at) => {
// First writer wins, as everywhere else here: two rows of one name is a
// corrupt list, and the first is what every other index resolves to.
const key = typeof contig === 'string' ? contig : contig.name
if (!built.has(key)) built.set(key, at)
})
POSITIONS.set(contigs, built)
return built
}
/**
* How a match reads in a sentence, for the info panel and the panel's own bar.
*
* Every tier gets its own words rather than a generic "matched loosely",
* because the whole point of carrying the tier is that a reader can decide
* whether to believe it — and "the `chr` prefix" and "the accession's version"
* warrant very different amounts of belief.
*/
export function describeTier(tier: MatchTier): string {
switch (tier) {
case 'exact':
return 'the same name'
case 'case':
return 'the same name, in another case'
case 'decorated':
return 'the same accession, undecorated'
case 'prefix':
return 'the chr prefix'
case 'padded':
return 'leading zeros'
case 'roman':
return 'Roman numerals'
case 'organelle':
return 'an organelle spelled another way'
case 'accession':
return 'the accession'
case 'version':
return 'the same accession at another version'
}
}
|