1#![allow(unused_imports)]
18#![allow(unused_unsafe)]
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct AlignmentScore {
25 pub score: i32,
26}
27
28#[derive(Debug, Clone)]
30pub struct AlignmentResult {
31 pub score: i32,
33 pub aligned_query: Vec<u8>,
35 pub aligned_target: Vec<u8>,
37 pub identity_pct: f32,
39 pub num_matches: usize,
40 pub num_gaps: usize,
41}
42
43#[derive(Debug, Clone, Copy)]
45pub struct GapPenalty {
46 pub open: i32,
47 pub extend: i32,
48}
49
50impl Default for GapPenalty {
51 fn default() -> Self {
52 Self {
53 open: -11,
54 extend: -1,
55 }
56 }
57}
58
59#[derive(Debug, Clone, Copy)]
61pub struct NucleotideMatrix {
62 pub match_score: i32,
63 pub mismatch_score: i32,
64}
65
66impl Default for NucleotideMatrix {
67 fn default() -> Self {
68 Self {
69 match_score: 2,
70 mismatch_score: -3,
71 }
72 }
73}
74
75static BLOSUM62_ORDER: &[u8] = b"ACDEFGHIKLMNPQRSTVWY";
79
80#[rustfmt::skip]
81static BLOSUM62: [[i8; 20]; 20] = [
82[ 4, -1, -2, -1, -2, 0, -2, -1, -1, -1, -1, -2, -1, -1, -1, 1, 0, 0, -3, -2], [-1, 9, -3, -4, -2, -3, -3, -1, -3, -1, -1, -3, -3, -3, -3, -1, -1, -1, -2, -2], [-2, -3, 6, 2, -3, -1, -1, -3, -1, -4, -3, 1, -1, 0, -2, 0, -1, -3, -4, -3], [-1, -4, 2, 5, -3, -2, 0, -3, 1, -3, -2, 0, -1, 2, 0, 0, -1, -2, -3, -2], [-2, -2, -3, -3, 6, -3, -1, 0, -3, 0, 0, -3, -4, -3, -3, -2, -2, -1, 1, 3], [ 0, -3, -1, -2, -3, 6, -2, -4, -2, -4, -3, 0, -2, -2, -2, 0, -2, -3, -2, -3], [-2, -3, -1, 0, -1, -2, 8, -3, -1, -3, -2, 1, -2, 0, 0, -1, -2, -3, -2, 2], [-1, -1, -3, -3, 0, -4, -3, 4, -3, 2, 1, -3, -3, -3, -3, -2, -1, 3, -3, -1], [-1, -3, -1, 1, -3, -2, -1, -3, 5, -2, -1, 0, -1, 1, 2, 0, -1, -2, -3, -2], [-1, -1, -4, -3, 0, -4, -3, 2, -2, 4, 2, -3, -3, -2, -2, -2, -1, 1, -2, -1], [-1, -1, -3, -2, 0, -3, -2, 1, -1, 2, 5, -2, -2, 0, -1, -1, -1, 1, -1, -1], [-2, -3, 1, 0, -3, 0, 1, -3, 0, -3, -2, 6, -2, 0, 0, 1, 0, -3, -4, -2], [-1, -3, -1, -1, -4, -2, -2, -3, -1, -3, -2, -2, 7, -1, -2, -1, -1, -2, -4, -3], [-1, -3, 0, 2, -3, -2, 0, -3, 1, -2, 0, 0, -1, 5, 1, 0, -1, -2, -2, -1], [-1, -3, -2, 0, -3, -2, 0, -3, 2, -2, -1, 0, -2, 1, 5, -1, -1, -3, -3, -2], [ 1, -1, 0, 0, -2, 0, -1, -2, 0, -2, -1, 1, -1, 0, -1, 4, 1, -2, -3, -2], [ 0, -1, -1, -1, -2, -2, -2, -1, -1, -1, -1, 0, -1, -1, -1, 1, 5, 0, -2, -2], [ 0, -1, -3, -2, -1, -3, -3, 3, -2, 1, 1, -3, -2, -2, -3, -2, 0, 4, -3, -1], [-3, -2, -4, -3, 1, -2, -2, -3, -3, -2, -1, -4, -4, -2, -3, -3, -2, -3, 11, 2], [-2, -2, -3, -2, 3, -3, 2, -1, -2, -1, -1, -2, -3, -1, -2, -2, -2, -1, 2, 7], ];
104
105#[inline]
106fn blosum62_idx(aa: u8) -> Option<usize> {
107 BLOSUM62_ORDER
108 .iter()
109 .position(|&c| c == aa.to_ascii_uppercase())
110}
111
112#[inline]
114pub fn blosum62_score(a: u8, b: u8) -> i32 {
115 match (blosum62_idx(a), blosum62_idx(b)) {
116 (Some(i), Some(j)) => BLOSUM62[i][j] as i32,
117 _ => -4,
118 }
119}
120
121const MAX_SEQ_LEN: usize = 50_000;
125
126pub fn smith_waterman(
129 query: &[u8],
130 target: &[u8],
131 gap: GapPenalty,
132 score_fn: impl Fn(u8, u8) -> i32,
133) -> AlignmentResult {
134 let m = query.len();
135 let n = target.len();
136 if m == 0 || n == 0 || m > MAX_SEQ_LEN || n > MAX_SEQ_LEN {
137 return empty_result();
138 }
139
140 let neg_inf = i32::MIN / 2;
141
142 let mut h = vec![vec![0i32; n + 1]; m + 1];
144 let mut e = vec![vec![neg_inf; n + 1]; m + 1];
145 let mut f = vec![vec![neg_inf; n + 1]; m + 1];
146
147 let mut tb = vec![vec![0u8; n + 1]; m + 1];
149
150 let mut best_score = 0i32;
151 let mut best_i = 0usize;
152 let mut best_j = 0usize;
153
154 for i in 1..=m {
155 for j in 1..=n {
156 e[i][j] = (h[i][j - 1].saturating_add(gap.open + gap.extend))
157 .max(e[i][j - 1].saturating_add(gap.extend));
158 f[i][j] = (h[i - 1][j].saturating_add(gap.open + gap.extend))
159 .max(f[i - 1][j].saturating_add(gap.extend));
160
161 let diag = h[i - 1][j - 1].saturating_add(score_fn(query[i - 1], target[j - 1]));
162 let cell = diag.max(e[i][j]).max(f[i][j]).max(0);
163 h[i][j] = cell;
164
165 tb[i][j] = if cell == 0 {
166 0
167 } else if cell == diag {
168 1
169 } else if cell == e[i][j] {
170 2
171 } else {
172 3
173 };
174
175 if cell > best_score {
176 best_score = cell;
177 best_i = i;
178 best_j = j;
179 }
180 }
181 }
182
183 traceback_local(&h, &tb, query, target, best_i, best_j, best_score)
184}
185
186fn traceback_local(
187 h: &[Vec<i32>],
188 tb: &[Vec<u8>],
189 query: &[u8],
190 target: &[u8],
191 mut i: usize,
192 mut j: usize,
193 score: i32,
194) -> AlignmentResult {
195 let mut aq = Vec::new();
196 let mut at = Vec::new();
197 let mut matches = 0usize;
198 let mut gaps = 0usize;
199
200 while i > 0 && j > 0 && h[i][j] > 0 {
201 match tb[i][j] {
202 1 => {
203 aq.push(query[i - 1]);
204 at.push(target[j - 1]);
205 if query[i - 1].eq_ignore_ascii_case(&target[j - 1]) {
206 matches += 1;
207 }
208 i -= 1;
209 j -= 1;
210 }
211 2 => {
212 aq.push(b'-');
213 at.push(target[j - 1]);
214 gaps += 1;
215 j -= 1;
216 }
217 3 => {
218 aq.push(query[i - 1]);
219 at.push(b'-');
220 gaps += 1;
221 i -= 1;
222 }
223 _ => break,
224 }
225 }
226 aq.reverse();
227 at.reverse();
228 let aln_len = aq.len();
229 AlignmentResult {
230 score,
231 identity_pct: if aln_len > 0 {
232 100.0 * matches as f32 / aln_len as f32
233 } else {
234 0.0
235 },
236 aligned_query: aq,
237 aligned_target: at,
238 num_matches: matches,
239 num_gaps: gaps,
240 }
241}
242
243fn empty_result() -> AlignmentResult {
244 AlignmentResult {
245 score: 0,
246 aligned_query: vec![],
247 aligned_target: vec![],
248 identity_pct: 0.0,
249 num_matches: 0,
250 num_gaps: 0,
251 }
252}
253
254pub fn needleman_wunsch(
258 query: &[u8],
259 target: &[u8],
260 gap: GapPenalty,
261 score_fn: impl Fn(u8, u8) -> i32,
262) -> AlignmentResult {
263 let m = query.len();
264 let n = target.len();
265 if m == 0 || n == 0 || m > MAX_SEQ_LEN || n > MAX_SEQ_LEN {
266 return empty_result();
267 }
268 let g = gap.open + gap.extend;
269 let mut dp = vec![vec![0i32; n + 1]; m + 1];
270 for i in 0..=m {
271 dp[i][0] = i as i32 * g;
272 }
273 for j in 0..=n {
274 dp[0][j] = j as i32 * g;
275 }
276
277 for i in 1..=m {
278 for j in 1..=n {
279 let sub = dp[i - 1][j - 1] + score_fn(query[i - 1], target[j - 1]);
280 let del = dp[i - 1][j] + g;
281 let ins = dp[i][j - 1] + g;
282 dp[i][j] = sub.max(del).max(ins);
283 }
284 }
285
286 let mut aq = Vec::new();
287 let mut at = Vec::new();
288 let mut matches = 0usize;
289 let mut gaps = 0usize;
290 let (mut i, mut j) = (m, n);
291
292 while i > 0 || j > 0 {
293 if i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + score_fn(query[i - 1], target[j - 1]) {
294 aq.push(query[i - 1]);
295 at.push(target[j - 1]);
296 if query[i - 1].eq_ignore_ascii_case(&target[j - 1]) {
297 matches += 1;
298 }
299 i -= 1;
300 j -= 1;
301 } else if i > 0 && (j == 0 || dp[i][j] == dp[i - 1][j] + g) {
302 aq.push(query[i - 1]);
303 at.push(b'-');
304 gaps += 1;
305 i -= 1;
306 } else {
307 aq.push(b'-');
308 at.push(target[j - 1]);
309 gaps += 1;
310 j -= 1;
311 }
312 }
313 aq.reverse();
314 at.reverse();
315 let aln_len = aq.len();
316 AlignmentResult {
317 score: dp[m][n],
318 identity_pct: if aln_len > 0 {
319 100.0 * matches as f32 / aln_len as f32
320 } else {
321 0.0
322 },
323 aligned_query: aq,
324 aligned_target: at,
325 num_matches: matches,
326 num_gaps: gaps,
327 }
328}
329
330pub fn align_nucleotide(query: &[u8], target: &[u8]) -> AlignmentResult {
334 let mat = NucleotideMatrix::default();
335 smith_waterman(query, target, GapPenalty::default(), move |a, b| {
336 if a.to_ascii_uppercase() == b.to_ascii_uppercase() {
337 mat.match_score
338 } else {
339 mat.mismatch_score
340 }
341 })
342}
343
344pub fn align_protein(query: &[u8], target: &[u8]) -> AlignmentResult {
346 smith_waterman(query, target, GapPenalty::default(), blosum62_score)
347}
348
349pub fn align_sequences(query: &[u8], target: &[u8]) -> AlignmentScore {
351 #[cfg(all(feature = "neon_simd_unroll", target_arch = "x86_64"))]
352 {
353 return simd_align_x86_64(query, target);
354 }
355
356 #[cfg(all(feature = "neon_simd_unroll", target_arch = "aarch64"))]
357 {
358 return simd_align_aarch64(query, target);
359 }
360
361 AlignmentScore {
362 score: align_nucleotide(query, target).score,
363 }
364}
365
366pub fn kmer_frequencies(sequence: &[u8], k: usize) -> Vec<(u64, u32)> {
370 if k == 0 || k > sequence.len() {
371 return vec![];
372 }
373 let mut counts = std::collections::HashMap::<u64, u32>::new();
374 for window in sequence.windows(k) {
375 let hash = window.iter().fold(0xcbf29ce484222325u64, |h, &b| {
376 (h ^ b.to_ascii_uppercase() as u64).wrapping_mul(0x100000001b3)
377 });
378 *counts.entry(hash).or_insert(0) += 1;
379 }
380 let mut out: Vec<(u64, u32)> = counts.into_iter().collect();
381 out.sort_unstable_by_key(|&(h, _)| h);
382 out
383}
384
385pub fn minhash_sketch(sequence: &[u8], k: usize, sketch_size: usize) -> Vec<u64> {
387 let mut hashes: Vec<u64> = kmer_frequencies(sequence, k)
388 .into_iter()
389 .map(|(h, _)| h)
390 .collect();
391 hashes.sort_unstable();
392 hashes.truncate(sketch_size);
393 hashes
394}
395
396pub fn jaccard_similarity(a: &[u64], b: &[u64]) -> f32 {
398 if a.is_empty() && b.is_empty() {
399 return 1.0;
400 }
401 let intersection = a.iter().filter(|&&x| b.binary_search(&x).is_ok()).count();
402 let union = a.len() + b.len() - intersection;
403 if union == 0 {
404 1.0
405 } else {
406 intersection as f32 / union as f32
407 }
408}
409
410pub const MAX_PHYLO_TAXA: usize = 64;
415
416#[derive(Debug, Clone, Copy, PartialEq)]
421pub struct PhyloMerge {
422 pub cluster_a: u16,
423 pub cluster_b: u16,
424 pub height: f32,
425 pub merged_id: u16,
426}
427
428pub fn build_upgma_tree(distances: &[f32], n: usize, out: &mut [PhyloMerge]) -> usize {
438 if n < 2 || n > MAX_PHYLO_TAXA || distances.len() < n * n || out.len() < n - 1 {
439 return 0;
440 }
441
442 let mut d = [[0f32; MAX_PHYLO_TAXA]; MAX_PHYLO_TAXA];
444 for i in 0..n {
445 for j in 0..n {
446 d[i][j] = distances[i * n + j];
447 }
448 }
449 let mut active = [true; MAX_PHYLO_TAXA];
450 let mut size = [1u32; MAX_PHYLO_TAXA];
451 let mut id = [0u16; MAX_PHYLO_TAXA]; for (i, slot) in id.iter_mut().enumerate().take(n) {
453 *slot = i as u16;
454 }
455
456 let mut written = 0usize;
457 let mut next_id = n as u16;
458
459 for _ in 0..n - 1 {
460 let mut best = f32::INFINITY;
462 let mut bi = 0usize;
463 let mut bj = 0usize;
464 for i in 0..n {
465 if !active[i] {
466 continue;
467 }
468 for j in (i + 1)..n {
469 if active[j] && d[i][j] < best {
470 best = d[i][j];
471 bi = i;
472 bj = j;
473 }
474 }
475 }
476
477 out[written] = PhyloMerge {
478 cluster_a: id[bi],
479 cluster_b: id[bj],
480 height: best / 2.0, merged_id: next_id,
482 };
483 written += 1;
484
485 let (si, sj) = (size[bi] as f32, size[bj] as f32);
488 for k in 0..n {
489 if k == bi || k == bj || !active[k] {
490 continue;
491 }
492 let merged = (si * d[bi][k] + sj * d[bj][k]) / (si + sj);
493 d[bi][k] = merged;
494 d[k][bi] = merged;
495 }
496 size[bi] += size[bj];
497 id[bi] = next_id;
498 active[bj] = false;
499 next_id += 1;
500 }
501
502 written
503}
504
505#[derive(Debug, Clone, PartialEq, Eq)]
508pub enum SequenceAlphabet {
509 DNA,
510 RNA,
511 Protein,
512 Unknown,
513}
514
515#[derive(Debug, Clone)]
516pub struct FastaRecord {
517 pub header: String,
518 pub sequence: Vec<u8>,
519 pub alphabet: SequenceAlphabet,
520 pub is_valid: bool,
521 pub invalid_chars: Vec<char>,
522}
523
524pub fn validate_fasta_record(header: &str, sequence: &[u8]) -> FastaRecord {
526 let dna_alphabet: &[u8] = b"ACGTNacgtn-";
527 let rna_alphabet: &[u8] = b"ACGUNacgun-";
528 let protein_alphabet: &[u8] = b"ACDEFGHIKLMNPQRSTVWYXacdefghiklmnpqrstvwyx*-";
529
530 let is_dna = sequence.iter().all(|c| dna_alphabet.contains(c));
531 let is_rna = sequence.iter().all(|c| rna_alphabet.contains(c));
532 let is_protein = sequence.iter().all(|c| protein_alphabet.contains(c));
533
534 let mut invalid: Vec<char> = sequence
535 .iter()
536 .filter(|c| !protein_alphabet.contains(c))
537 .map(|&c| c as char)
538 .collect();
539 invalid.dedup();
540
541 let alphabet = if is_dna {
542 SequenceAlphabet::DNA
543 } else if is_rna {
544 SequenceAlphabet::RNA
545 } else if is_protein {
546 SequenceAlphabet::Protein
547 } else {
548 SequenceAlphabet::Unknown
549 };
550
551 FastaRecord {
552 header: header.to_string(),
553 sequence: sequence.to_vec(),
554 is_valid: invalid.is_empty() && !sequence.is_empty() && !header.is_empty(),
555 invalid_chars: invalid,
556 alphabet,
557 }
558}
559
560#[inline]
565pub fn tanimoto_similarity(fp_a: &[u64], fp_b: &[u64]) -> f32 {
566 assert_eq!(fp_a.len(), fp_b.len(), "fingerprint lengths must match");
567 let intersection: u32 = fp_a
568 .iter()
569 .zip(fp_b)
570 .map(|(a, b)| (a & b).count_ones())
571 .sum();
572 let union: u32 = fp_a
573 .iter()
574 .zip(fp_b)
575 .map(|(a, b)| (a | b).count_ones())
576 .sum();
577 if union == 0 {
578 1.0
579 } else {
580 intersection as f32 / union as f32
581 }
582}
583
584#[inline]
586pub fn dice_similarity(fp_a: &[u64], fp_b: &[u64]) -> f32 {
587 assert_eq!(fp_a.len(), fp_b.len());
588 let intersection: u32 = fp_a
589 .iter()
590 .zip(fp_b)
591 .map(|(a, b)| (a & b).count_ones())
592 .sum();
593 let sum_a: u32 = fp_a.iter().map(|a| a.count_ones()).sum();
594 let sum_b: u32 = fp_b.iter().map(|b| b.count_ones()).sum();
595 if sum_a + sum_b == 0 {
596 1.0
597 } else {
598 2.0 * intersection as f32 / (sum_a + sum_b) as f32
599 }
600}
601
602#[cfg(all(feature = "neon_simd_unroll", target_arch = "x86_64"))]
605pub fn simd_align_x86_64(query: &[u8], target: &[u8]) -> AlignmentScore {
607 if std::is_x86_feature_detected!("avx2") {
608 unsafe { simd_align_x86_64_avx2(query, target) }
610 } else {
611 AlignmentScore {
612 score: align_nucleotide(query, target).score,
613 }
614 }
615}
616
617#[cfg(all(feature = "neon_simd_unroll", target_arch = "x86_64"))]
618#[target_feature(enable = "avx2")]
619unsafe fn simd_align_x86_64_avx2(query: &[u8], target: &[u8]) -> AlignmentScore {
620 use std::arch::x86_64::*;
621 let min_len = query.len().min(target.len());
622 let mut score = 0i32;
623 let mut i = 0;
624
625 while i + 32 <= min_len {
627 let q_vec = _mm256_loadu_si256(query.as_ptr().add(i) as *const __m256i);
628 let t_vec = _mm256_loadu_si256(target.as_ptr().add(i) as *const __m256i);
629 let cmp = _mm256_cmpeq_epi8(q_vec, t_vec);
630 let mask = _mm256_movemask_epi8(cmp);
631 let matches = mask.count_ones() as i32;
632 let mismatches = 32 - matches;
633
634 score += matches * 2;
635 score -= mismatches * 3;
636 i += 32;
637 }
638
639 if i < min_len {
640 score += align_nucleotide(&query[i..], &target[i..]).score;
641 }
642 AlignmentScore { score }
643}
644
645#[cfg(all(feature = "neon_simd_unroll", target_arch = "aarch64"))]
646pub fn simd_align_aarch64(query: &[u8], target: &[u8]) -> AlignmentScore {
648 #[cfg(target_feature = "neon")]
649 unsafe {
650 use std::arch::aarch64::*;
651 let min_len = query.len().min(target.len());
652 let mut score = 0i32;
653 let mut i = 0;
654
655 while i + 16 <= min_len {
657 let q_vec = vld1q_u8(query.as_ptr().add(i));
658 let t_vec = vld1q_u8(target.as_ptr().add(i));
659 let cmp = vceqq_u8(q_vec, t_vec);
660
661 let mut v = [0u8; 16];
662 vst1q_u8(v.as_mut_ptr(), cmp);
663 let mut matches = 0;
664 for &b in &v {
665 if b == 0xFF {
666 matches += 1;
667 }
668 }
669 let mismatches = 16 - matches;
670
671 score += matches * 2;
672 score -= mismatches * 3;
673 i += 16;
674 }
675
676 if i < min_len {
677 score += align_nucleotide(&query[i..], &target[i..]).score;
678 }
679 return AlignmentScore { score };
680 }
681
682 #[cfg(not(target_feature = "neon"))]
683 AlignmentScore {
684 score: align_nucleotide(query, target).score,
685 }
686}
687
688pub fn translate_dna_to_protein(dna: &[u8], out: &mut [u8]) -> usize {
694 let mut written = 0;
695 for i in (0..dna.len()).step_by(3) {
696 if i + 2 >= dna.len() {
697 break;
698 }
699 if written >= out.len() {
700 break;
701 }
702
703 let codon = (
704 dna[i].to_ascii_uppercase(),
705 dna[i + 1].to_ascii_uppercase(),
706 dna[i + 2].to_ascii_uppercase(),
707 );
708 let aa = match codon {
709 (b'G', b'C', _) => b'A', (b'T', b'G', b'C') | (b'T', b'G', b'T') => b'C', (b'G', b'A', b'C') | (b'G', b'A', b'T') => b'D', (b'G', b'A', b'A') | (b'G', b'A', b'G') => b'E', (b'T', b'T', b'C') | (b'T', b'T', b'T') => b'F', (b'G', b'G', _) => b'G', (b'C', b'A', b'C') | (b'C', b'A', b'T') => b'H', (b'A', b'T', b'C') | (b'A', b'T', b'T') | (b'A', b'T', b'A') => b'I', (b'A', b'A', b'A') | (b'A', b'A', b'G') => b'K', (b'C', b'T', _) | (b'T', b'T', b'A') | (b'T', b'T', b'G') => b'L', (b'A', b'T', b'G') => b'M', (b'A', b'A', b'C') | (b'A', b'A', b'T') => b'N', (b'C', b'C', _) => b'P', (b'C', b'A', b'A') | (b'C', b'A', b'G') => b'Q', (b'C', b'G', _) | (b'A', b'G', b'A') | (b'A', b'G', b'G') => b'R', (b'T', b'C', _) | (b'A', b'G', b'C') | (b'A', b'G', b'T') => b'S', (b'A', b'C', _) => b'T', (b'G', b'T', _) => b'V', (b'T', b'G', b'G') => b'W', (b'T', b'A', b'C') | (b'T', b'A', b'T') => b'Y', (b'T', b'A', b'A') | (b'T', b'A', b'G') | (b'T', b'G', b'A') => b'*', _ => b'X', };
732 out[written] = aa;
733 written += 1;
734 }
735 written
736}
737
738pub fn calculate_isoelectric_point(protein: &[u8]) -> f64 {
743 let c_term = 1; let n_term = 1; let mut d = 0; let mut e = 0; let mut c = 0; let mut y = 0; let mut h = 0; let mut k = 0; let mut r = 0; for &aa in protein {
754 match aa.to_ascii_uppercase() {
755 b'D' => d += 1,
756 b'E' => e += 1,
757 b'C' => c += 1,
758 b'Y' => y += 1,
759 b'H' => h += 1,
760 b'K' => k += 1,
761 b'R' => r += 1,
762 _ => {}
763 }
764 }
765
766 let pka_c_term = 3.65;
768 let pka_d = 3.90;
769 let pka_e = 4.07;
770 let pka_c = 8.18;
771 let pka_y = 10.46;
772
773 let pka_n_term = 8.20;
774 let pka_h = 6.04;
775 let pka_k = 10.53;
776 let pka_r = 12.48;
777
778 let net_charge = |ph: f64| -> f64 {
779 let neg = (c_term as f64) / (1.0 + 10.0_f64.powf(pka_c_term - ph))
780 + (d as f64) / (1.0 + 10.0_f64.powf(pka_d - ph))
781 + (e as f64) / (1.0 + 10.0_f64.powf(pka_e - ph))
782 + (c as f64) / (1.0 + 10.0_f64.powf(pka_c - ph))
783 + (y as f64) / (1.0 + 10.0_f64.powf(pka_y - ph));
784
785 let pos = (n_term as f64) / (1.0 + 10.0_f64.powf(ph - pka_n_term))
786 + (h as f64) / (1.0 + 10.0_f64.powf(ph - pka_h))
787 + (k as f64) / (1.0 + 10.0_f64.powf(ph - pka_k))
788 + (r as f64) / (1.0 + 10.0_f64.powf(ph - pka_r));
789
790 pos - neg
791 };
792
793 let mut low = 0.0;
795 let mut high = 14.0;
796 for _ in 0..50 {
797 let mid = (low + high) / 2.0;
798 let charge = net_charge(mid);
799 if charge > 0.0 {
800 low = mid;
801 } else {
802 high = mid;
803 }
804 }
805 (low + high) / 2.0
806}
807
808pub fn predict_peptide_cleavage(protein: &[u8], out_indices: &mut [usize]) -> usize {
814 let mut count = 0;
815 for i in 0..protein.len() {
816 if count >= out_indices.len() {
817 break;
818 }
819 let aa = protein[i].to_ascii_uppercase();
820 if aa == b'K' || aa == b'R' {
821 if i + 1 < protein.len() && protein[i + 1].to_ascii_uppercase() == b'P' {
822 continue; }
824 out_indices[count] = i;
825 count += 1;
826 }
827 }
828 count
829}
830
831#[cfg(test)]
834mod tests {
835 use super::*;
836
837 #[test]
838 fn sw_identical_nucleotide() {
839 let r = align_nucleotide(b"ACGTACGT", b"ACGTACGT");
840 assert!(r.score > 0);
841 assert!((r.identity_pct - 100.0).abs() < 0.01);
842 }
843
844 #[test]
845 fn sw_one_mismatch() {
846 let r = align_nucleotide(b"ACGTACGT", b"ACGTCCGT");
847 assert!(r.score > 0);
848 assert!(r.identity_pct > 80.0);
849 }
850
851 #[test]
852 fn blosum62_diagonal_positive() {
853 for aa in b"ACDEFGHIKLMNPQRSTVWY" {
854 assert!(
855 blosum62_score(*aa, *aa) > 0,
856 "diagonal should be positive for {}",
857 *aa as char
858 );
859 }
860 }
861
862 #[test]
863 fn blosum62_w_max_diagonal() {
864 assert_eq!(blosum62_score(b'W', b'W'), 11);
865 }
866
867 #[test]
868 fn protein_align_identical() {
869 let r = align_protein(b"ACDEFGHIK", b"ACDEFGHIK");
870 assert!(r.score > 0);
871 assert!((r.identity_pct - 100.0).abs() < 0.01);
872 }
873
874 #[test]
875 fn nw_global_fills_gaps() {
876 let mat = NucleotideMatrix::default();
877 let r = needleman_wunsch(b"ACGT", b"ACGTTTT", GapPenalty::default(), move |a, b| {
878 if a.to_ascii_uppercase() == b.to_ascii_uppercase() {
879 mat.match_score
880 } else {
881 mat.mismatch_score
882 }
883 });
884 assert_eq!(r.aligned_query.len(), r.aligned_target.len());
885 }
886
887 #[test]
888 fn kmer_frequency_counts() {
889 let f = kmer_frequencies(b"ATCGATCG", 3);
890 assert!(!f.is_empty());
891 let total: u32 = f.iter().map(|&(_, c)| c).sum();
892 assert_eq!(total, 6); }
894
895 #[test]
896 fn fasta_dna_valid() {
897 let r = validate_fasta_record(">seq1", b"ATCGATCG");
898 assert_eq!(r.alphabet, SequenceAlphabet::DNA);
899 assert!(r.is_valid);
900 }
901
902 #[test]
903 fn invalid_fasta_alphabets() {
904 let rec = validate_fasta_record(">test", b"ATCGXZATCG");
905 assert!(!rec.is_valid);
906 }
907
908 #[test]
909 fn test_translate_dna() {
910 let dna = b"ATGGCCATTGTAATGGGCCGCTGAAAGGGTGCCCGATAG";
911 let mut out = [0u8; 100];
912 let n = translate_dna_to_protein(dna, &mut out);
913 assert_eq!(&out[..n], b"MAIVMGR*KGAR*");
914 }
915
916 #[test]
917 fn test_isoelectric_point() {
918 let protein = b"MGRKGAR"; let pi = calculate_isoelectric_point(protein);
920 assert!(pi > 10.0, "pI was {}", pi);
921 }
922
923 #[test]
924 fn test_peptide_cleavage() {
925 let protein = b"MGRKGAR"; let mut out = [0usize; 10];
927 let n = predict_peptide_cleavage(protein, &mut out);
928 assert_eq!(n, 3);
929 assert_eq!(&out[..n], &[2, 3, 6]);
930 }
931
932 #[test]
933 fn fasta_invalid_chars() {
934 let r = validate_fasta_record(">seq2", b"ATCG123");
935 assert!(!r.is_valid);
936 assert!(!r.invalid_chars.is_empty());
937 }
938
939 #[test]
940 fn tanimoto_identical() {
941 let fp = vec![0xFFFFFFFFFFFFFFFFu64; 2];
942 assert!((tanimoto_similarity(&fp, &fp) - 1.0).abs() < 1e-6);
943 }
944
945 #[test]
946 fn tanimoto_disjoint() {
947 let a = vec![0x00000000FFFFFFFFu64];
948 let b = vec![0xFFFFFFFF00000000u64];
949 assert!((tanimoto_similarity(&a, &b)).abs() < 1e-6);
950 }
951
952 #[test]
953 fn upgma_builds_the_expected_nested_tree() {
954 #[rustfmt::skip]
962 let d = [
963 0.0, 2.0, 6.0, 6.0,
964 2.0, 0.0, 6.0, 6.0,
965 6.0, 6.0, 0.0, 4.0,
966 6.0, 6.0, 4.0, 0.0,
967 ];
968 let mut out = [PhyloMerge {
969 cluster_a: 0,
970 cluster_b: 0,
971 height: 0.0,
972 merged_id: 0,
973 }; 8];
974 let n = build_upgma_tree(&d, 4, &mut out);
975 assert_eq!(n, 3, "n-1 merges for 4 taxa");
976
977 assert_eq!((out[0].cluster_a, out[0].cluster_b), (0, 1));
979 assert!((out[0].height - 1.0).abs() < 1e-6);
980 assert_eq!(out[0].merged_id, 4);
981
982 assert_eq!((out[1].cluster_a, out[1].cluster_b), (2, 3));
984 assert!((out[1].height - 2.0).abs() < 1e-6);
985 assert_eq!(out[1].merged_id, 5);
986
987 assert_eq!((out[2].cluster_a, out[2].cluster_b), (4, 5));
989 assert!((out[2].height - 3.0).abs() < 1e-6);
990 assert_eq!(out[2].merged_id, 6, "last merged_id is the root");
991 }
992
993 #[test]
994 fn upgma_rejects_degenerate_input() {
995 let mut out = [PhyloMerge {
996 cluster_a: 0,
997 cluster_b: 0,
998 height: 0.0,
999 merged_id: 0,
1000 }; 8];
1001 assert_eq!(build_upgma_tree(&[0.0], 1, &mut out), 0, "n<2 rejected");
1002 let d = [0.0, 1.0, 1.0, 0.0];
1004 let mut tiny = [PhyloMerge {
1005 cluster_a: 0,
1006 cluster_b: 0,
1007 height: 0.0,
1008 merged_id: 0,
1009 }; 0];
1010 assert_eq!(
1011 build_upgma_tree(&d, 2, &mut tiny),
1012 0,
1013 "undersized out rejected"
1014 );
1015 }
1016}