use crate::{create, fresh_dir, Opts, R};
use flate2::read::MultiGzDecoder;
use std::fs::File;
use std::io::{BufRead, BufReader};
use rayon::prelude::*;
use rustc_hash::{FxBuildHasher, FxHashMap};
use std::hash::BuildHasher;
use std::io::Write;
use std::path::Path;
pub fn run(o: &Opts) -> R<()> {
let dir = Path::new(o.str("dir"));
let (k, min_aa): (usize, usize) = (o.get("kmer_size")?, o.get("kmer_min_aa")?);
let (dir_arg, out) = (o.str("dir_arg"), o.str("output")); println!(" --- STEP 1: k-mer simplification\n input dir: {dir_arg}\n output dir: {}\n kmer size: {k}\n kmer nb aa: {min_aa}",
if out.is_empty() { "." } else { out });
if !dir.is_dir() { return Err(format!("the directory '{dir_arg}' does not exist").into()) }
fresh_dir("dir_step1")?;
let mut files: Vec<String> = std::fs::read_dir(dir)?
.filter_map(|e| e.ok())
.filter(|e| e.path().is_file())
.map(|e| e.file_name().to_string_lossy().to_string())
.filter(|n| is_proteome(n))
.collect();
if files.is_empty() { return Err(format!("no proteome file (.fas/.fasta/.faa, optionally .gz) in {dir_arg}").into()) }
files.sort();
let names: Vec<Vec<String>> = files.par_iter()
.map(|f| Ok(read_fasta(&dir.join(f))?.into_iter().map(|(n, _)| n).collect()))
.collect::<R<_>>()?;
let mut offset = vec![0u32];
for n in &names { offset.push(offset.last().unwrap() + n.len() as u32) }
println!(" {} input files\n {} sequences", files.len(), offset.last().unwrap());
let mut seen: FxHashMap<&str, usize> = FxHashMap::default();
let mut dupli = vec![];
for (i, ns) in names.iter().enumerate() {
for n in ns {
if let Some(&j) = seen.get(n.as_str()) { dupli.push(format!("{n}\t{}\t{}", files[j], files[i])) }
else { seen.insert(n, i); }
}
}
if !dupli.is_empty() {
println!(" WARNING: some protein names are present multiple times, see {}", crate::shown("dir_step1/duplicate_names.txt").display());
std::fs::write("dir_step1/duplicate_names.txt", format!("#protein_name\tfile1\tfile2\n{}\n", dupli.join("\n")))?;
}
let reps: Vec<Vec<u32>> = files.par_iter().enumerate().map(|(i, f)| {
let seqs: Vec<Vec<u8>> = read_fasta(&dir.join(f))?.into_iter().map(|(_, s)| s).collect();
let rep = simplify(&seqs, k, min_aa);
let mut out = create(format!("dir_step1/{i}.fas"))?;
for (j, s) in seqs.iter().enumerate() {
if rep[j] as usize == j { writeln!(out, ">{}\n{}", offset[i] + j as u32, String::from_utf8_lossy(s))? }
}
Ok(rep.into_iter().map(|r| r + offset[i]).collect())
}).collect::<R<_>>()?;
let mut species = create("dir_step1/species.tsv")?;
let mut prots = create("dir_step1/proteins.tsv")?;
let mut log = create("dir_step1/log_step1.txt")?;
writeln!(log, "#index\tfile_name\tnb_initial\tnb_final")?;
let mut nb_final = 0;
for (i, f) in files.iter().enumerate() {
writeln!(species, "{i}\t{f}")?;
let kept = reps[i].iter().enumerate().filter(|&(j, &r)| r == offset[i] + j as u32).count();
writeln!(log, "{i}\t{f}\t{}\t{kept}", names[i].len())?;
nb_final += kept;
for (j, n) in names[i].iter().enumerate() {
writeln!(prots, "{}\t{i}\t{}\t{n}", offset[i] + j as u32, reps[i][j])?;
}
}
println!(" -> {nb_final} proteins saved for the next step\n");
Ok(())
}
fn is_proteome(name: &str) -> bool {
let n = name.to_lowercase();
let n = n.strip_suffix(".gz").unwrap_or(&n);
[".fas", ".fasta", ".faa"].iter().any(|e| n.ends_with(e))
}
pub fn read_fasta(path: &Path) -> R<Vec<(String, Vec<u8>)>> {
let f = File::open(path).map_err(|e| format!("cannot open {}: {e}", path.display()))?;
let reader: Box<dyn BufRead> = if path.to_string_lossy().to_lowercase().ends_with(".gz") {
Box::new(BufReader::new(MultiGzDecoder::new(f)))
} else {
Box::new(BufReader::new(f))
};
let mut v: Vec<(String, Vec<u8>)> = vec![];
for l in reader.lines() {
let l = l?;
let l = l.trim_end();
if let Some(h) = l.strip_prefix('>') {
v.push((h.split_whitespace().next().unwrap_or("").to_string(), vec![]));
} else if let Some(last) = v.last_mut() {
last.1.extend_from_slice(l.as_bytes());
}
}
Ok(v)
}
fn simplify(seqs: &[Vec<u8>], k: usize, min_aa: usize) -> Vec<u32> {
let bits = |x: usize| usize::BITS - x.leading_zeros(); let sb = bits(seqs.len().saturating_sub(1));
let pb = bits(seqs.iter().map(|s| s.len().saturating_sub(k)).max().unwrap_or(0));
let top = u64::MAX.checked_shl(sb + pb).unwrap_or(0);
let hash = |x: u64| x & top;
let seq = |x: u64| ((x >> pb) & ((1u64 << sb) - 1)) as usize;
let start = |x: u64| (x & ((1u64 << pb) - 1)) as usize;
let mut kmers: Vec<u64> = Vec::with_capacity(seqs.iter().map(|s| (s.len() + 1).saturating_sub(k)).sum());
for (i, s) in seqs.iter().enumerate() {
let (mut cnt, mut distinct, mut bad) = ([0u32; 256], 0, 0);
for j in 0..s.len() {
let c = s[j] as usize;
if cnt[c] == 0 { distinct += 1 }
cnt[c] += 1;
if c == b'X' as usize || c == b'*' as usize { bad += 1 }
if j >= k {
let c = s[j - k] as usize;
cnt[c] -= 1;
if cnt[c] == 0 { distinct -= 1 }
if c == b'X' as usize || c == b'*' as usize { bad -= 1 }
}
if j + 1 >= k && distinct >= min_aa && bad == 0 {
let start = j + 1 - k;
kmers.push(FxBuildHasher.hash_one(&s[start..=j]) & top | (i as u64) << pb | start as u64);
}
}
}
let kmer = |x: u64| &seqs[seq(x)][start(x)..start(x) + k];
kmers.sort_unstable_by(|&a, &b| hash(a).cmp(&hash(b)).then_with(|| kmer(a).cmp(kmer(b)))); let mut uf: Vec<u32> = (0..seqs.len() as u32).collect();
for w in kmers.windows(2) {
if hash(w[0]) == hash(w[1]) && kmer(w[0]) == kmer(w[1]) {
let (a, b) = (find(&mut uf, seq(w[0]) as u32), find(&mut uf, seq(w[1]) as u32));
uf[a.max(b) as usize] = a.min(b); }
}
let mut best: Vec<u32> = (0..seqs.len() as u32).collect();
for i in 0..seqs.len() {
let r = find(&mut uf, i as u32) as usize;
if seqs[i].len() > seqs[best[r] as usize].len() { best[r] = i as u32 }
}
(0..seqs.len()).map(|i| best[find(&mut uf, i as u32) as usize]).collect()
}
fn find(uf: &mut [u32], mut x: u32) -> u32 {
while uf[x as usize] != x {
uf[x as usize] = uf[uf[x as usize] as usize];
x = uf[x as usize];
}
x
}
#[cfg(test)]
mod tests {
#[test]
fn proteome_extensions() {
for n in ["a.fas", "a.FASTA", "a.faa.gz", "a.Faa.GZ"] { assert!(super::is_proteome(n), "{n}") }
for n in ["a.fa", "a.txt", "a.gz", "fasta"] { assert!(!super::is_proteome(n), "{n}") }
}
#[test]
fn simplify_keeps_longest() {
let a = b"ACDEFGHIKLMNPQ".to_vec();
let mut b = a.clone();
b.extend(b"RSTVW");
let c = b"WWWWWWWWWWWWWW".to_vec(); let d = b"ACDEXGHIKLMNPQ".to_vec(); let rep = super::simplify(&[a, b, c.clone(), c, d], 10, 5);
assert_eq!(rep, vec![1, 1, 2, 3, 4]);
}
}