How a new Internet-Security/Anti-Virus startup prepares its malware database? I have seen some new products that are able to detect viruses that were on the wild 10-15 years back.
Anti-Virus companies have two aspects to handle,
Signatures themselves are pretty well standardized (with quantified false-positive characteristics).
So, a new company would pickup a standard database from some source and 'run' their custom translators to convert it to a database that will work with their implementation.
A few references for further reading,